A ledger is a singly linked list of integer amounts. It is cleaned by this exact process:
process the nodes from front to back, attaching each one to the end of a kept chain
(which starts empty). Right after attaching a node, if the kept chain now ends with a run of
one or more consecutive nodes whose values add up to 0, cut that whole run out of the kept
chain. (At any moment at most one such run can exist, so the process is well defined.)
Return the head of the kept chain after every node has been processed (None if nothing is
left). Re-link the existing nodes; do not build a new list.
Examples
Input: head = 4 -> 1 -> -1 -> 2 -> 5 -> -7 -> 9
Output: 4 -> 9
Explanation: after -1 the run 1, -1 is cut; after -7 the run 2, 5, -7 is cut.
Input: head = 3 -> 4 -> -4 -> 1 -> -1 -> -3 -> 5
Output: 5
Input: head = 0 -> 0
Output: None
Constraints
0 <= number of nodes <= 3 * 10**4-10**4 <= node value <= 10**4- Target: O(n) time. Re-scanning the kept chain after every node is too slow for the large tests.
Goals
- Detect a zero-sum suffix with a dictionary of running totals
- Splice out a removed run in O(1)
- Undo dictionary entries for nodes that were cut away