  # LeetCode - Merge Nodes in Between Zeros

## 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.

Problem statement taken from: https://leetcode.com/problems/merge-nodes-in-between-zeros

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 * 10^5].
- 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.
``````

### Explanation

We can solve the problem using two-pointers. According to the problem statement, the list start and end nodes are zero. We can set one pointer current to head->next and another pointer node to head.

We keep moving the pointer current to the next node until the node value is not equal to zero. While iterating, we keep adding the value of these nodes and assign it to the sum variable. We create a node with this sum value and assign node->next to the new ListNode.

We keep iterating the above approach till we reach the end of the linked list.

Let's check the algorithm for this approach.

``````- if head == NULL
- return NULL

- set ListNode* current = head->next
sum = 0

- loop while current
- loop while current->val != 0
- update sum = sum + current->val
- update current = current->val
- while end

- set node->next = new ListNode(sum)
- node = node->next

- update sum = 0
- current = current->next
- while end

``````

The time complexity of the above approach is O(n), and the space complexity is O(1).

Let's check our algorithm in C++, Golang, and JavaScript.

#### C++ solution

``````class Solution {
public:
return NULL;
}

int sum = 0;

while(current) {
while(current->val != 0) {
sum += current->val;
current = current->next;
}

node->next = new ListNode(sum);
node = node->next;

sum = 0;
current = current->next;
}

}
};``````

#### Golang solution

``````func mergeNodes(head *ListNode) *ListNode {
return nil
}

sum := 0

for current != nil {
for current.Val != 0 {
sum += current.Val
current = current.Next
}

node.Next = &ListNode{Val: sum}
node = node.Next

sum = 0
current = current.Next
}

}``````

#### JavaScript solution

``````var mergeNodes = function(head) {
return null;
}

let sum = 0;

while(current) {
while(current.val != 0) {
sum += current.val;
current = current.next;
}

node.next = new ListNode(sum);
node = node.next;

sum = 0;
current = current.next;
}

};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: head -> [0, 3, 1, 0, 4, 5, 2, 0]

Step 1: if head == NULL
false

-> 3
-> 0
sum = 0

Step 3: while current
true

while current->val != 0
3 != 0
true

sum = sum + current->val
= 0 + 3
= 3

current = current->next
-> 1

while current->val != 0
1 != 0
true

sum = sum + current->val
= 3 + 1
= 4

current = current->next
-> 0

while current->val != 0
0 != 0
false

node->next = new ListNode(sum)
= new ListNode(4)

The list is now
[0, 4]

node = node->next
-> 4

sum = 0
current = current->next
-> 4

Step 4: while current
true

while current->val != 0
4 != 0
true

sum = sum + current->val
= 0 + 4
= 4

current = current->next
-> 5

while current->val != 0
5 != 0
true

sum = sum + current->val
= 4 + 5
= 9

current = current->next
-> 2

while current->val != 0
2 != 0
true

sum = sum + current->val
= 9 + 2
= 11

current = current->next
-> 0

while current->val != 0
0 != 0
false

node->next = new ListNode(sum)
= new ListNode(11)

The list is now
[0, 4, 11]

node = node->next
-> 11

sum = 0
current = current->next
-> nil

Step 5: while current
false