336. Fold Between Zeros
A tram line logs passenger counts as a chain of nodes. The log starts and ends with a node holding 0, which marks a depot visit, and between two consecutive depot nodes there is a non-empty stretch of positive counts, one per stop. No two depot nodes are adjacent.
Given the head of the log, fold every stretch between two consecutive depot nodes into one node holding the sum of that stretch, and drop all depot nodes. Return the head of the new chain, in the original order. For example, the log 0, 3, 2, 0, 4, 0 turns into 5, 4. A log that is a lone 0 contains no stretch, so the result is empty. The log can hold up to 100,000 nodes.
Example 1
- Input:
- head = [0,3,2,0,5,0,1,1,1,0]
- Output:
- [5,5,3]
- Explanation:
The stretches are 3 + 2 = 5, then 5, then 1 + 1 + 1 = 3. Result: [5, 5, 3].
Example 2
- Input:
- head = [0,7,0]
- Output:
- [7]
- Explanation:
There is one stretch, holding only 7. Result: [7].
Constraints
1 ≤ chain length ≤ 105
The first and the last node have value 0; no two adjacent nodes are both 0
1 ≤ every other node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n) for the output chain (O(1) if you reuse nodes)