Remove Zero Sum Consecutive Nodes from Linked List

Problem

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.)

Examples

Example 1

1
2
3
4
5
6
7



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

Example 2

1
2
3
4
5
6

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

Example 3

1
2
3
4
5
6

    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.

Solution

Method 1 - Prefix Sum with Hash Map

Intuition

If we keep a running prefix sum as we traverse the list, whenever the same prefix sum occurs at two nodes, the nodes in between sum to zero and can be removed. We can use a hash map to record the last occurrence of each prefix sum.

Approach

Use a dummy node before head to handle removals at the start.
First pass: Traverse the list, recording the last node for each prefix sum.
Second pass: Traverse again, and for each node, set its next pointer to the next node after the last occurrence of the same prefix sum.
Return dummy.next.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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

ListNode* removeZeroSumSublists(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    unordered_map<int, ListNode*> prefix;
    int sum = 0;
    for (ListNode* node = &dummy; node; node = node->next) {
        sum += node->val;
        prefix[sum] = node;
    }
    sum = 0;
    for (ListNode* node = &dummy; node; node = node->next) {
        sum += node->val;
        node->next = prefix[sum]->next;
    }
    return dummy.next;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


type ListNode struct {
    Val  int
    Next *ListNode
}
func removeZeroSumSublists(head *ListNode) *ListNode {
    dummy := &ListNode{0, head}
    prefix := map[int]*ListNode{}
    sum := 0
    for node := dummy; node != nil; node = node.Next {
        sum += node.Val
        prefix[sum] = node
    }
    sum = 0
    for node := dummy; node != nil; node = node.Next {
        sum += node.Val
        node.Next = prefix[sum].Next
    }
    return dummy.Next
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        Map<Integer, ListNode> prefix = new HashMap<>();
        int sum = 0;
        for (ListNode node = dummy; node != null; node = node.next) {
            sum += node.val;
            prefix.put(sum, node);
        }
        sum = 0;
        for (ListNode node = dummy; node != null; node = node.next) {
            sum += node.val;
            node.next = prefix.get(sum).next;
        }
        return dummy.next;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class ListNode(var `val`: Int) {
    var next: ListNode? = null
}
fun removeZeroSumSublists(head: ListNode?): ListNode? {
    val dummy = ListNode(0)
    dummy.next = head
    val prefix = mutableMapOf<Int, ListNode>()
    var sum = 0
    var node: ListNode? = dummy
    while (node != null) {
        sum += node.`val`
        prefix[sum] = node
        node = node.next
    }
    sum = 0
    node = dummy
    while (node != null) {
        sum += node.`val`
        node.next = prefix[sum]?.next
        node = node.next
    }
    return dummy.next
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeZeroSumSublists(head: ListNode) -> ListNode:
    dummy = ListNode(0, head)
    prefix = {}
    s = 0
    node = dummy
    while node:
        s += node.val
        prefix[s] = node
        node = node.next
    s = 0
    node = dummy
    while node:
        s += node.val
        node.next = prefix[s].next
        node = node.next
    return dummy.next

1
2


// ListNode struct and function signature omitted for brevity
// Use a similar approach as above with HashMap and two passes

 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


class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}
function removeZeroSumSublists(head: ListNode | null): ListNode | null {
    const dummy = new ListNode(0, head);
    const prefix = new Map<number, ListNode>();
    let sum = 0;
    let node: ListNode | null = dummy;
    while (node) {
        sum += node.val;
        prefix.set(sum, node);
        node = node.next;
    }
    sum = 0;
    node = dummy;
    while (node) {
        sum += node.val;
        node.next = prefix.get(sum)!.next;
        node = node.next;
    }
    return dummy.next;
}

Complexity

⏰ Time complexity: O(N), where N is the number of nodes in the list.
🧺 Space complexity: O(N), for the prefix sum map.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 - Prefix Sum with Hash Map#

Intuition#

Approach#

Code#

Complexity#