Add up between the zeros
A list is divided by zeros into segments - replace each segment with one node holding its sum. About 14 minutes.
Flush at each zero
The list begins and ends with a zero, and zeros divide it into segments of positive numbers. Each segment should become one node holding the segment's sum.
Walk from the node after the first zero. Add each positive value to a running sum. When you reach a zero, the segment is finished, so write a new node with the sum and reset the sum to zero.
if cur.val == 0:
s = 0 # a new segment
else:
s += cur.valThe first segment is 2, 6. The sum is 8.
Where to start and end
The first node is a zero that opens the first segment, so it does not close anything. Start the walk at head.next.
The last node is a zero that closes the last segment, so the final segment is flushed by the same rule and nothing is left over at the end. Collect the new nodes behind a dummy, and return the dummy's next.
dummy = tail = ListNode() cur = head.next
The list is 0, 7, 0. What is the result?
- AA single node holding 7
- BA single node holding 0
- CTwo nodes, 0 and 7
Show the answer
A single node holding 7. There is one segment, 7, and the final zero closes it.
Merge nodes between zeros
You are given the head of a linked list that begins and ends with a 0, has no two zeros next to each other, and has only positive values between zeros. For every segment between two consecutive zeros, replace the segment by one node holding the sum of its values. Return the head of the new list, which contains no zeros.
head = [0, 3, 1, 0, 4, 5, 2, 0] → [4, 11]
3 ≤ number of nodes ≤ 5,000 · 0 ≤ node.val ≤ 1,000 · begins and ends with 0, with positive values between