Merge Nodes in Between Zeros solution and explanation
Google
9 more videos on this problem
Merge Nodes in Between Zeros - Leetcode 2181 - PythonNeetCodeIO · 11:24 · 8K views
Merge Nodes in Between Zeros | 2 Approaches | Leap Of Faith | Leetcode 2181 | codestorywithMIKcodestorywithMIK · 21:36 · 6K views
✅ Merge Nodes in Between Zeros - LeetCode 2181 - Single Pass - O(N) - Explained in DetailLeet Logics · 8:27 · 1K views
Merge Nodes in Between Zeros | LeetCode 2181 | Coders CampCoders Camp · 11:33 · 1K views
Leetcode | 2181. Merge Nodes in Between Zeros | Medium | JavaDeveloper Docs · 5:37 · 317 views
2181. Merge Nodes in Between ZerosPolliverse · 10:26 · 106 views
2181.Merge Nodes in Between Zeros [EASY win]!Robin hood · 23:45 · 41 views
2181. Merge Nodes in Between Zeros | Leetcode | Python - DSATechnosier · 18:59 · 41 views
LeetCode Problem 2181. Merge Nodes in Between Zeros - solution with TypeScript & JavaScriptRuslan Tsykaliak · 5:38 · 27 views
Merge Nodes in Between Zeros | LeetCode 2181 | Java Code | Developer CoderDeveloper Coder · 9:26 · 26 views
The problem
You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list will have Node.val == 0.
For every two consecutive 0's, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0's.
Return the head of the modified linked list.
Example 1:
Input: head = [0,3,1,0,4,5,2,0] Output: [4,11] Explanation: The above figure represents the given linked list. The modified list contains - The sum of the nodes marked in green: 3 + 1 = 4. - The sum of the nodes marked in red: 4 + 5 + 2 = 11.
Example 2:
Input: head = [0,1,0,3,0,2,2,0] Output: [1,3,4] Explanation: The above figure represents the given linked list. The modified list contains - The sum of the nodes marked in green: 1 = 1. - The sum of the nodes marked in red: 3 = 3. - The sum of the nodes marked in yellow: 2 + 2 = 4.
Constraints:
- The number of nodes in the list is in the range
[3, 2 * 105]. 0 <= Node.val <= 1000- There are no two consecutive nodes with
Node.val == 0. - The beginning and end of the linked list have
Node.val == 0.
Approach overview
Problem Overview: The linked list starts and ends with 0. Between every pair of zeros are positive integers. Your task is to merge each segment by summing the values between the zeros and creating a new node containing that sum.
Approach 1: Single Pass with Dummy Node (O(n) time, O(1) space)
This approach scans the list once while maintaining a running sum of values between zero nodes. When you encounter a 0, the current accumulated sum represents a completed segment. Create a new node with this sum and append it to a result list using a dummy head pointer. Reset the sum and continue traversing until the list ends. The key idea is treating each zero as a boundary marker while iterating through the linked list. Because each node is visited exactly once and no additional data structures are required beyond a few pointers, the algorithm runs in O(n) time with O(1) extra space.
This pattern is common in simulation-style linked list problems. Instead of modifying the original nodes, you construct a clean result list that stores only the computed segment sums. The dummy node simplifies edge cases, especially when inserting the first merged value.
Approach 2: Recursive Merging and Accumulation (O(n) time, O(n) space)
The recursive solution processes segments one at a time using function calls to accumulate values until the next zero appears. Start from the node after the first zero and recursively sum nodes until another zero is reached. When that boundary appears, create a new node containing the accumulated sum and recursively process the rest of the list. Each recursive call handles one segment of numbers between zeros.
This method highlights the natural segmentation of the problem. Each recursive frame represents a segment being merged, which makes the logic easy to reason about. However, recursion adds O(n) stack usage in the worst case. For very long lists, the iterative approach is typically safer and more memory efficient. The recursion pattern is still useful for practicing divide-style traversal on recursive linked list problems.
Recommended for interviews: The single-pass iterative approach with a dummy node is the expected solution. It demonstrates strong pointer manipulation, efficient traversal, and constant extra space usage. Explaining the recursive alternative can show deeper understanding, but interviewers usually prefer the iterative solution because it avoids stack overhead and mirrors real production code patterns.
Approach 1: Single Pass with Dummy Node
This approach involves traversing the linked list using a single pass while keeping a temporary sum of node values between consecutive zeros. We use a dummy node to help simplify edge cases related to list modifications.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeNodes(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
tail = dummy
sum = 0
current = head.next
while current:
if current.val == 0:
tail.next = ListNode(sum)
tail = tail.next
sum = 0
else:
sum += current.val
current = current.next
return dummy.nextclass ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
public ListNode mergeNodes(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int sum = 0;
for (ListNode node = head.next; node != null; node = node.next) {
if (node.val == 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
} else {
sum += node.val;
}
}
return dummy.next;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
ListNode* mergeNodes(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
int sum = 0;
for (ListNode* ptr = head->next; ptr != nullptr; ptr = ptr->next) {
if (ptr->val == 0) {
tail->next = new ListNode(sum);
tail = tail->next;
sum = 0;
} else {
sum += ptr->val;
}
}
return dummy->next;
}function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function mergeNodes(head) {
let dummy = new ListNode(0);
let tail = dummy;
let sum = 0;
let current = head.next; // Skip the leading zero
while (current) {
if (current.val === 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
} else {
sum += current.val;
}
current = current.next;
}
return dummy.next;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode* next;
};
struct ListNode* mergeNodes(struct ListNode* head) {
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = NULL;
struct ListNode* tail = dummy;
int sum = 0;
struct ListNode* iterator = head->next; // skip the first 0
while (iterator != NULL) {
if (iterator->val == 0) {
tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
tail = tail->next;
tail->val = sum;
tail->next = NULL;
sum = 0; // reset sum
} else {
sum += iterator->val;
}
iterator = iterator->next;
}
// Free the initial zero node
free(head);
return dummy->next; // return the new list, omitting the leading zero node
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode MergeNodes(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int sum = 0;
for (ListNode node = head.next; node != null; node = node.next) {
if (node.val == 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
} else {
sum += node.val;
}
}
return dummy.next;
}
}The Python solution is straightforward and simple, making use of a dummy node to handle insertions. The sum is calculated by traversing from the head's next node (since head is guaranteed to be zero).
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Recursive Merging and Accumulation
Another approach we can take involves recursion to solve each segment between the zeros sequentially. Though iterative is usually preferred for this problem, recursion can offer a more functional programming perspective.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeNodes(self, head: ListNode) -> ListNode:
def sumNodes(node, currentSum=0, tail=None):
if not node:
return
if node.val == 0 and currentSum > 0:
tail.next = ListNode(currentSum)
tail = tail.next
currentSum = 0
else:
currentSum += node.val
sumNodes(node.next, currentSum, tail)
dummy = ListNode(0)
sumNodes(head.next, 0, dummy)
return dummy.nextclass ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
private void recursiveSum(ListNode node, int[] sum, ListNode tail) {
if (node == null) return;
if (node.val == 0 && sum[0] > 0) {
tail.next = new ListNode(sum[0]);
tail = tail.next;
sum[0] = 0;
} else if (node.val != 0) {
sum[0] += node.val;
}
recursiveSum(node.next, sum, tail);
}
public ListNode mergeNodes(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int[] sum = new int[1]; // Use array to mimic pass by reference
recursiveSum(head.next, sum, tail);
return dummy.next;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
void recursiveSum(ListNode* node, int& sum, ListNode*& tail) {
if (!node) return;
if (node->val == 0 && sum > 0) {
tail->next = new ListNode(sum);
tail = tail->next;
sum = 0;
} else if (node->val != 0) {
sum += node->val;
}
recursiveSum(node->next, sum, tail);
}
ListNode* mergeNodes(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
int sum = 0;
recursiveSum(head->next, sum, tail);
return dummy->next;
}function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function mergeNodes(head) {
function sumNodes(current, sum, tail) {
if (!current) return;
if (current.val === 0 && sum > 0) {
tail.next = new ListNode(sum);
tail = tail.next;
sum = 0;
} else if (current.val !== 0) {
sum += current.val;
}
sumNodes(current.next, sum, tail);
}
let dummy = new ListNode(0);
sumNodes(head.next, 0, dummy);
return dummy.next;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode* next;
};
void recursiveSum(struct ListNode* head, int* currentSum, struct ListNode** lastNode) {
if (!head) return;
if (head->val == 0) {
if (*currentSum > 0) {
(*lastNode)->next = (struct ListNode*)malloc(sizeof(struct ListNode));
*lastNode = (*lastNode)->next;
(*lastNode)->val = *currentSum;
(*lastNode)->next = NULL;
*currentSum = 0;
}
} else {
*currentSum += head->val;
}
recursiveSum(head->next, currentSum, lastNode);
}
struct ListNode* mergeNodes(struct ListNode* head) {
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = NULL;
struct ListNode* lastNode = dummy;
int currentSum = 0;
recursiveSum(head->next, ¤tSum, &lastNode);
return dummy->next;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
private void RecursiveMerge(ListNode node, ref int sum, ref ListNode last) {
if (node == null) return;
if (node.val == 0 && sum > 0) {
last.next = new ListNode(sum);
last = last.next;
sum = 0;
} else if (node.val != 0) {
sum += node.val;
}
RecursiveMerge(node.next, ref sum, ref last);
}
public ListNode MergeNodes(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode last = dummy;
int sum = 0;
RecursiveMerge(head.next, ref sum, ref last);
return dummy.next;
}
}The recursive approach in Python illustrates a functional approach to breaking down the segments between zeros, using recursive calls to manage nodes and sums.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Simulation
We define a dummy head node dummy, a pointer tail pointing to the current node, and a variable s to record the sum of the values of the current nodes.
Next, we traverse the linked list starting from the second node. If the value of the current node is not 0, we add it to s. Otherwise, we add s to the node after tail, set s to 0, and update tail to the next node.
Finally, we return the node next to dummy.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeNodes(head: ListNode | null): ListNode | null {
const dummy = new ListNode();
let tail = dummy;
let s = 0;
for (let cur = head.next; cur; cur = cur.next) {
if (cur.val) {
s += cur.val;
} else {
tail.next = new ListNode(s);
tail = tail.next;
s = 0;
}
}
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeNodes(head *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
s := 0
for cur := head.Next; cur != nil; cur = cur.Next {
if cur.Val != 0 {
s += cur.Val
} else {
tail.Next = &ListNode{Val: s}
tail = tail.Next
s = 0
}
}
return dummy.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn merge_nodes(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(0));
let mut tail = &mut dummy;
let mut s = 0;
let mut cur = head.unwrap().next;
while let Some(mut node) = cur {
if node.val != 0 {
s += node.val;
} else {
tail.next = Some(Box::new(ListNode::new(s)));
tail = tail.next.as_mut().unwrap();
s = 0;
}
cur = node.next.take();
}
dummy.next
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Single Pass with Dummy Node | Time Complexity: O(n) |
| Recursive Merging and Accumulation | Time Complexity: O(n) |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Pass with Dummy Node | O(n) | O(1) | Best general solution. Efficient traversal with constant memory. |
| Recursive Merging and Accumulation | O(n) | O(n) | Useful for practicing recursion or when modeling segments recursively. |
Frequently asked questions
Is Merge Nodes in Between Zeros easy or hard?
Merge Nodes in Between Zeros is rated Medium difficulty on LeetCode. The main challenge is correctly handling segment boundaries and linked list pointer operations. Once you recognize that zeros act as delimiters, the problem reduces to a straightforward linear traversal.
Merge Nodes in Between Zeros Python/Java solution
Both Python and Java implementations follow the same idea: traverse the linked list, track the sum between zero nodes, and construct a new linked list with the merged sums. The logic remains identical across languages, differing only in syntax for node creation and pointer updates.
How to solve Merge Nodes in Between Zeros in O(n)?
Iterate through the linked list and maintain a running sum of node values until a zero node appears. When you encounter the zero boundary, create a new node containing the accumulated sum and attach it to the result list. Reset the sum and continue until the traversal ends.
What is the best approach for Merge Nodes in Between Zeros?
The single-pass iterative approach with a dummy node is the best solution. Traverse the linked list once, accumulate values between zero nodes, and append the computed sum to a result list. This method runs in O(n) time and uses O(1) extra space, making it both efficient and interview-friendly.
Is Merge Nodes in Between Zeros asked at Google/Amazon/Meta?
Linked list traversal and segment aggregation problems like this frequently appear in technical interviews at companies such as Amazon, Google, and Meta. Variations often test pointer manipulation, list traversal, and efficient handling of boundary conditions.
What data structure is used in Merge Nodes in Between Zeros?
The primary data structure is a singly linked list. The algorithm relies on pointer traversal and accumulation logic to process segments between sentinel nodes (zeros). No additional structures such as arrays or hash maps are required for the optimal approach.
What is the time complexity of Merge Nodes in Between Zeros?
The optimal solution runs in O(n) time where n is the number of nodes in the linked list. Each node is visited exactly once during traversal while accumulating values between zeros. Space complexity is O(1) if you build the result list iteratively without recursion.