LeetCode 1171. Remove Zero Sum Consecutive Nodes from LinkedList

, , , , , ,

Question

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.

Solution

We need to maintain the hashmap to record the prefix sum to ListNode.

  • if we didn’t seen it before, just record.
  • otherwise, it shows the range sum between it would be zero, and we have to move our current pointer, at the end, we can skip the range we find.

Code

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
// time:O(n) space:O(n)
public ListNode removeZeroSumSublists(ListNode head) {
        // use prefix sum.
        // if we meet the same prefix, it means 0 sums between it.
        if (head == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;
        int prefix = 0;
        HashMap<Integer, ListNode> map = new HashMap<>();
        while (curr != null) {
            prefix += curr.val;
            if (map.containsKey(prefix)) {
                curr = map.get(prefix).next;
                int p = prefix + curr.val;
                while (p != prefix) {
                    map.remove(p);
                    curr = curr.next;
                    p += curr.val;
                }
                // skip
                map.get(prefix).next = curr.next;
            } else {
                map.put(prefix, curr);
            }
            curr = curr.next;
        }
        return dummy.next;
    }

Reference