How to Remove Zero Sum Consecutive Nodes from Linked List using Prefix Sum?

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences. After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:
Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:
Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:
The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

Hints:
Convert the linked list into an array.
While you can find a non-empty subarray with sum = 0, erase it.
Convert the array into a linked list.

Remove Zero-Sum Link Node usig Prefix/Cumulative Sum

The prefix sum can be stored and retrieved using a hash map. We accumulate the sum (as key), and store its node as value in the hash map. Then, when a sum occurs, we know the interval between two link nodes sum to zero. We can then re-point the previous node’s next to the next node which effectively removes the nodes between.

At the meantime, if the Cumulative sum from the begining is zero, we need to reset the head and recursively remove the zero sum lists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* newHead = head;
        unordered_map<int, ListNode*> prefix;
        int sum = 0;
        bool flag = false;        
        while (head) {
            sum += head->val;
            if (sum == 0) {
                newHead = head->next;
                flag = true;
                break;
            } else if (prefix.find(sum) == prefix.end()) {
                prefix[sum] = head;
            } else {
                prefix[sum]->next = head->next;
                flag = true;
            }
            head = head->next;
        }
        if (flag) {
            return removeZeroSumSublists(newHead);
        }
        return newHead;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* newHead = head;
        unordered_map<int, ListNode*> prefix;
        int sum = 0;
        bool flag = false;        
        while (head) {
            sum += head->val;
            if (sum == 0) {
                newHead = head->next;
                flag = true;
                break;
            } else if (prefix.find(sum) == prefix.end()) {
                prefix[sum] = head;
            } else {
                prefix[sum]->next = head->next;
                flag = true;
            }
            head = head->next;
        }
        if (flag) {
            return removeZeroSumSublists(newHead);
        }
        return newHead;
    }
};

The above C++ code to remove the zero sum nodes for a given linked list runs at O(N) time and require O(N) space – using a hash map.

–EOF (The Ultimate Computing & Technology Blog) —