Cancel out
Delete every run of consecutive nodes that adds up to zero, using running totals to spot where a run starts and ends. About 20 minutes.
Equal totals mean a zero run
Keep a running total as you walk. Suppose the total is 3 after one node and 3 again after a later node. The nodes in between must have added nothing, so they sum to zero and can be deleted.
The dummy node in front of the head counts as total 0. This makes a run starting at the very first node work like any other.
s = 0
node = head
while node:
s += node.val
print(s)
node = node.nextThe totals go 5, then 7. Nothing repeats yet.
Two passes
A first pass remembers, for each running total, the last node where it occurred. A second pass walks again and, at each node, links it to whatever follows the last node with the same total. Any zero run in between is jumped over at once.
Taking the last node for each total also handles runs inside runs. After deleting one run, more may appear, and the jump already skips them.
last = {}
last[s] = node # the later one winsRunning totals after each node are 2, 5, 2, 7. Which nodes cancel out?
- AThe 2nd and 3rd nodes, between the two totals of 2
- BThe 1st and 2nd nodes
- CNone
Show the answer
The 2nd and 3rd nodes, between the two totals of 2. The total went from 2 back to 2, so the nodes in between add to zero.
Remove zero-sum runs
Given the head of a linked list, repeatedly delete a run of consecutive nodes whose values add up to 0, until no such run is left. Different deletion orders can leave different lists, so follow this rule: each time, delete the run that starts earliest in the list, and if several runs start there, the longest of them. Return the head of the final list.
head = [1, 2, -3, 3, 1] → [3, 1]
0 ≤ number of nodes ≤ 1,000 · -1,000 ≤ node.val ≤ 1,000