# Merge Nodes in Between Zeros
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/merge-nodes-in-between-zeros)
Canonical: https://scaleengineer.com/dsa/problems/merge-nodes-in-between-zeros
**Data structures:** Linked List
**Companies:** [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## 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:**

![](https://assets.glich.co/dsa/merge-nodes-in-between-zeros/image0.png) 

**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:**

![](https://assets.glich.co/dsa/merge-nodes-in-between-zeros/image1.png) 

**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`.

# Approaches
## Simulation with a New List
This approach involves iterating through the original linked list and building a new linked list to store the merged nodes. It's straightforward and doesn't alter the input list.
**Time:** O(N), where N is the number of nodes in the list. We perform a single pass through the list. · **Space:** O(M), where M is the number of segments between zeros. This is because we create a new node for each segment. In the worst case, M can be proportional to N, leading to O(N) space complexity.
**Pros:** Simple to understand and implement.; Does not modify the original input list.
**Cons:** Requires extra space to store the new list, which can be significant for large inputs.
### Explanation
We'll traverse the original list, keeping track of the sum of values in the current segment (between two zeros).
A dummy node is used to simplify the construction of the new list. A `tail` pointer will track the end of the new list.
We start iterating from the node after the initial zero.
For each node, if its value is not zero, we add it to a running sum.
When we encounter a zero, it signifies the end of a segment. We create a new node with the accumulated sum, append it to our new list, and reset the sum to zero for the next segment.
This process continues until we've traversed the entire original list. The final result is the list starting from the dummy node's `next` pointer.
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeNodes(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode newTail = dummy;
        ListNode current = head.next; // Skip the initial 0
        int currentSum = 0;

        while (current != null) {
            if (current.val == 0) {
                // End of a segment
                if (currentSum > 0) {
                    newTail.next = new ListNode(currentSum);
                    newTail = newTail.next;
                }
                currentSum = 0; // Reset for the next segment
            } else {
                // Accumulate sum
                currentSum += current.val;
            }
            current = current.next;
        }
        return dummy.next;
    }
}
```
### Algorithm
- Initialize a `dummy` node and a `newTail` pointer to build the result list.
- Initialize `currentSum = 0`.
- Iterate through the input list starting from `head.next`.
- If the current node's value is not 0, add it to `currentSum`.
- If the current node's value is 0, create a new node with `currentSum`, append it to the result list using `newTail`, and reset `currentSum` to 0.
- After the loop, return `dummy.next`.

## Recursive In-place Modification
This approach uses recursion to solve the problem by breaking it down into smaller subproblems. Each recursive call handles one segment (the nodes between two zeros), sums them up, and links to the result of the next segment.
**Time:** O(N), as each node is visited a constant number of times across all recursive calls. · **Space:** O(M), where M is the number of segments. This space is used by the recursion call stack. In the worst case, this can be O(N), which might lead to a `StackOverflowError` for very long lists.
**Pros:** In-place modification of nodes saves heap memory.; Can be an elegant and concise solution.
**Cons:** Risk of `StackOverflowError` for deep recursion levels (long lists).; Can be less intuitive than an iterative approach.
### Explanation
The main idea is to define a recursive function, say `solve(node)`, that takes a `0`-node as input and returns the head of the merged list for the part of the list that follows.
The base case for the recursion is when the node after the input `0`-node is `null`, which means we've reached the end of the list. In this case, we return `null`.
In the recursive step, we first move to the node after the input `0`-node. This is the start of a new segment. We can reuse this node to store the sum.
We then iterate forward from this node to find the next `0`, summing up the values along the way.
Once we find the next `0`, we update the value of the segment's starting node with the calculated sum.
The `next` pointer of this updated node is then set to the result of a recursive call on the `0`-node we just found.
The initial call from the main function will be `solve(head)`.
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeNodes(ListNode head) {
        // The first node is a 0, so we start processing from it.
        // The recursive function will handle the segments.
        return solve(head);
    }

    private ListNode solve(ListNode node) {
        // 'node' is the 0 before the segment we need to process.
        node = node.next; // Move to the first node of the segment.

        // Base case: if we are at the end of the list (after the last 0).
        if (node == null) {
            return null;
        }

        // Find the sum of the current segment.
        ListNode runner = node;
        int sum = 0;
        while (runner.val != 0) {
            sum += runner.val;
            runner = runner.next;
        }

        // 'runner' is now at the next 0.
        // The start of the segment 'node' will be the new merged node.
        node.val = sum;

        // The next merged node is the result of the recursion on the rest of the list.
        node.next = solve(runner);

        return node;
    }
}
```
### Algorithm
- Define a recursive function `solve(node)` that processes the list starting from a `0`-node.
- Base Case: If `node.next` is `null`, return `null`.
- Move to the start of the segment: `startNode = node.next`.
- Iterate from `startNode` to find the next `0`, calculating the sum of values.
- Update `startNode.val` with the calculated sum.
- Recursively call `solve` on the `0`-node that ends the current segment: `startNode.next = solve(zeroNode)`.
- Return `startNode`.
- The initial call is `solve(head)`.

## Iterative In-place Modification (Two Pointers)
This is the most optimal approach. It modifies the linked list in-place using two pointers, avoiding both the extra space of a new list and the recursion stack overhead. This results in O(1) extra space complexity.
**Time:** O(N), where N is the number of nodes. Although there are nested loops, each node is visited only a constant number of times by the `fast` pointer, resulting in a linear time complexity. · **Space:** O(1). The modification is done in-place, using only a few extra pointers. No significant extra space is required, regardless of the input size.
**Pros:** Extremely space-efficient with O(1) complexity.; Avoids recursion, thus no risk of stack overflow.; Efficient in terms of both time and space.
**Cons:** Modifies the original list, which might not be desirable in all contexts.; The pointer manipulation can be slightly more complex to follow than the new-list approach.
### Explanation
We use two pointers. Let's call them `modify` and `fast`.
The `modify` pointer will act as the tail of our new, condensed list. It will always point to the last valid merged node. We initialize it to `head`.
The `fast` pointer will iterate through the original list to find segments and calculate their sums. We initialize it to `head.next`.
The algorithm works by finding a segment (from one `0` to the next), calculating its sum, and then placing that sum into the node right after the one `modify` is pointing to.
In each step of the main loop, `fast` moves forward, accumulating a sum until it hits a `0`.
Once a `0` is found, we have the sum for the segment. We update the value of `modify.next` with this sum.
Then, we advance `modify` to `modify.next`, effectively extending our condensed list by one node.
The `fast` pointer is then advanced to the node after the `0` it just found, to start processing the next segment.
The loop continues until `fast` has traversed the entire list. Finally, we set `modify.next = null` to terminate the new list correctly. The result is `head.next`.
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeNodes(ListNode head) {
        // The first node (head) is a 0 and acts as a sentinel.
        // 'modify' will be the tail of the new list.
        ListNode modify = head;
        // 'fast' will traverse the list.
        ListNode fast = head.next;

        while (fast != null) {
            int sum = 0;
            // 'fast' is at the beginning of a segment.
            // Accumulate sum until the next 0.
            while (fast.val != 0) {
                sum += fast.val;
                fast = fast.next;
            }

            // 'fast' is now at a 0 node.
            // The node after 'modify' will store the sum.
            modify.next.val = sum;
            // Move 'modify' to this node.
            modify = modify.next;

            // Move 'fast' to the start of the next segment.
            fast = fast.next;
        }
        // Terminate the modified list.
        modify.next = null;
        
        // The new list starts after the sentinel 'head'.
        return head.next;
    }
}
```
### Algorithm
- Initialize `modify = head` to act as the tail of the result list, which is built starting from `head`.
- Initialize `fast = head.next` to traverse the list.
- Loop while `fast` is not null.
- Inside the loop, start a nested loop to find the next `0` and calculate the `sum` of the segment.
- Once the segment sum is calculated, store it in `modify.next.val`.
- Advance `modify` to `modify.next`.
- Advance `fast` past the `0` to the start of the next segment.
- After the main loop, set `modify.next = null` to correctly terminate the list.
- Return `head.next`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeNodes ( ListNode head ) { ListNode dummy = new ListNode (); int s = 0 ; ListNode tail = dummy ; for ( ListNode cur = head . next ; cur != null ; cur = cur . next ) { if ( cur . val != 0 ) { s += cur . val ; } else { tail . next = new ListNode ( s ); tail = tail . next ; s = 0 ; } } return dummy . next ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode * mergeNodes ( ListNode * head ) { ListNode * dummy = new ListNode (); ListNode * tail = dummy ; int s = 0 ; for ( ListNode * 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 ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def mergeNodes ( self , head : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = tail = ListNode () s = 0 cur = head . next while cur : if cur . val != 0 : s += cur . val else : tail . next = ListNode ( s ) tail = tail . next s = 0 cur = cur . next return dummy . next
```