Remove Zero Sum Consecutive Nodes from Linked List
Medium · Linked Lists · Hash Table · Linked List
Problem
You are given the head of a linked list of integers. While the list contains a run of consecutive nodes whose values add up to 0, delete that run. Stop when no such run is left, and return the head of what remains (None if nothing does).
Different deletion orders can end in different lists. Any final list you can reach this way is accepted.
Examples
Input: head = [2,-2,5,3,-3] Output: [5]
The runs [2, -2] and [3, -3] each sum to zero and are deleted, leaving 5.
Input: head = [4,1,-1,-4,6] Output: [6]
Once [1, -1] is gone, 4 and -4 are next to each other and cancel too.
Input: head = [1,2,3] Output: [1,2,3]
No run sums to zero, so the list is unchanged.
Constraints
- The list has between 1 and 1000 nodes
- -1000 <= Node.val <= 1000
Approaches
- Baseline: from every node, cut every run that cancels — time O(n²), space O(1)
Follow-up
Why does jumping to the last node with the same prefix sum leave no zero-sum run behind? After the jumps, the nodes that remain have prefix sums that are all different, and a zero-sum run would need two equal ones. The same "two equal prefix sums" idea answers "does any subarray sum to k?" with prefix − k in the map.
Related problems
Start free on Cariara · Coding problems · System design studio
