ลบโหนดที่ผลรวมเป็นศูนย์ติดต่อกันใน Linked List ด้วย C++

ปัญหา

ให้ Head ของ Linked List ลบ Subsequence ที่ติดกันซ้ำๆ จนกว่าจะไม่มี Subsequence ที่ผลรวมเป็น 0 คืน Head ของ List ที่เหลือ

ตัวอย่าง: [1,2,-3,3,1] → [3,1] (เพราะ 1+2-3=0 ถูกลบ เหลือ 3,1)

อัลกอริทึม (Prefix Sum + Hash Map)

1. สร้าง Dummy Node ชี้ Head
2. Pass 1: คำนวณ Prefix Sum เก็บ Map<Sum, Node*> (เก็บ Node สุดท้ายของแต่ละ Sum)
3. Pass 2: เดินจาก Dummy อีกครั้ง คำนวณ Prefix Sum เดิม หา Node สุดท้ายของ Sum เดียวกัน → ข้าม Node ระหว่างทาง

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* removeZeroSumSublists(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    
    unordered_map<int, ListNode*> prefix_sum;
    prefix_sum[0] = dummy;
    
    int sum = 0;
    // Pass 1: Build prefix sum map
    for (ListNode* cur = head; cur; cur = cur->next) {
        sum += cur->val;
        prefix_sum[sum] = cur; // เก็บ node สุดท้ายของ sum นี้
    }
    
    // Pass 2: Remove zero-sum sequences
    sum = 0;
    for (ListNode* cur = dummy; cur; cur = cur->next) {
        sum += cur->val;
        ListNode* target = prefix_sum[sum];
        if (target != cur) {
            cur->next = target->next; // ข้าม node ระหว่างทาง
        }
    }
    
    ListNode* result = dummy->next;
    delete dummy;
    return result;
}

// Helper functions
ListNode* make_list(vector<int> v) { ... }
void print_list(ListNode* head) { ... }

int main() {
    vector<int> v = {1, 2, -3, 3, 1};
    ListNode* head = make_list(v);
    print_list(removeZeroSumSublists(head)); // [3, 1]
    return 0;
}

ผลลัพธ์

[3, 1]

ความซับซ้อน

• Time: O(N) - เดิน 2 รอบ
• Space: O(N) - Hash Map เก็บ Prefix Sum