Skip to main content
Talentd

Merge Nodes in Between Zeros - Solution & Explanation

MediumLinked ListSimulation20 min readAsked at: Amazon, Microsoft, Oracle +2
Practice this problem

Problem Statement

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.

The solution uses a single traversal of the linked list. A dummy node is used to build the new list of merged node values. A temporary variable sum accumulates the values between two zeros. Once a zero is encountered, a new node with sum is appended to the resultant list, and sum is reset.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list as we traverse the list only once.
Space Complexity: O(1), excluding the space needed for the new output list.

Try this approach in the editor →

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.

This recursive approach involves a helper function that traverses the linked list, accumulating values between zeros. When a zero is encountered, a node is created with the accumulated sum (if any) and the values reset for subsequent segments.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) due to recursive stack space

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Single Pass with Dummy Node

Time Complexity: O(n), where n is the number of nodes in the linked list as we traverse the list only once.
Space Complexity: O(1), excluding the space needed for the new output list.

Recursive Merging and Accumulation

Time Complexity: O(n)
Space Complexity: O(n) due to recursive stack space

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Single Pass with Dummy NodeO(n)O(1)Best general solution. Efficient traversal with constant memory.
Recursive Merging and AccumulationO(n)O(n)Useful for practicing recursion or when modeling segments recursively.

Video Solution

Merge Nodes in Between Zeros - Leetcode 2181 - Python • NeetCodeIO • 8,239 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Merge Nodes in Between Zeros with our built-in code editor and test cases.

Practice on FleetCode
Previous

Linked List Components