Merge Nodes in Between Zeros — Problem & Solution
Merge Nodes in Between Zeros solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Merge Nodes in Between Zeros is a medium coding problem on simulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the head of a linked list of integers separated by zeros: the list both starts and ends with a node of value 0, and no two 0 nodes are adjacent.
For every stretch of nodes lying between two consecutive 0s, replace the whole stretch by a single node whose value is the sum of the stretch. The resulting list contains no 0 nodes at all. Return its head.
Example 1
Input: head = [0,4,2,0,7,0,1,1,1,0]
Output: [6,7,3]
Explanation: The stretches are [4,2], [7] and [1,1,1], summing to 6, 7 and 3.
Example 2
Input: head = [0,5,0]
Output: [5]
Explanation: A single stretch holding one node.
Example 3
Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: The stretches [3,1] and [4,5,2] sum to 4 and 11.
Constraints
The number of nodes in the list is in the range [3, 2 * 10^5]0 <= Node.val <= 1000There are no two consecutive nodes with Node.val == 0The first and the last nodes have Node.val == 0
Hints for Merge Nodes in Between Zeros
Hint 1
Every
0after the first closes one stretch, so a single pass with a running sum is enough.Hint 2
You do not need new nodes: the sums can be written into nodes the pass has already read.
Hint 3
There are fewer stretches than nodes read so far, so write each finished sum into the next node of the list from the front, and cut the list after the last one written.
How to solve Merge Nodes in Between Zeros
Scan once with a running sum, and every time a 0 closes a stretch write the sum into a node at the front of the list. The writer always trails the reader, so writing never destroys a value still to be read.
Approach
- Let
write = headandlast = null; start reading athead.nextwithsum = 0. - For each node: if its value is
0, storesuminwrite, rememberlast = write, movewriteon and resetsum; otherwise add the value tosum. - Cut the list after
last(last.next = null) and returnhead.
Why it works
When the k-th stretch closes, the reader has passed at least 2k nodes (each stretch holds at least one non-zero node plus its closing zero), while the writer stands at node k - 1. So the writer only overwrites nodes that were read already.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The leading
0opens the first stretch; it is not a separator that produces an empty sum. - Forgetting to cut the list after the last written sum leaves the old tail attached.
Reference solution
Python
from typing import Optional
def mergeNodes(head: Optional[ListNode]) -> Optional[ListNode]:
write, last = head, None
cur, s = head.next, 0
while cur:
if cur.val == 0:
write.val = s
last = write
write = write.next
s = 0
else:
s += cur.val
cur = cur.next
last.next = None
return headJava
public static ListNode mergeNodes(ListNode head) {
ListNode write = head, last = null;
int s = 0;
for (ListNode cur = head.next; cur != null; cur = cur.next) {
if (cur.val == 0) { write.val = s; last = write; write = write.next; s = 0; }
else s += cur.val;
}
last.next = null;
return head;
}C++
ListNode* mergeNodes(ListNode* head) {
ListNode *write = head, *last = nullptr;
int s = 0;
for (ListNode* cur = head->next; cur; cur = cur->next) {
if (cur->val == 0) { write->val = s; last = write; write = write->next; s = 0; }
else s += cur->val;
}
last->next = nullptr;
return head;
}JavaScript
var mergeNodes = function(head) {
var write = head, last = null, s = 0;
for (var cur = head.next; cur !== null; cur = cur.next) {
if (cur.val === 0) { write.val = s; last = write; write = write.next; s = 0; }
else s += cur.val;
}
last.next = null;
return head;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.