Formatted question description: https://leetcode.ca/all/2181.html

# 2181. Merge Nodes in Between Zeros (Medium)

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

.

**Similar Questions**:

## Solution 1.

```
// OJ: https://leetcode.com/problems/merge-nodes-in-between-zeros/
// Time: O(N)
// Space: O(1)
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
ListNode dummy, *tail = &dummy;
while (head) {
if (head->val == 0) head = head->next; // skip leading `0`
if (!head) break;
int sum = 0;
while (head->val != 0) { // sum numbers before the next `0`
sum += head->val;
head = head->next;
}
tail->next = new ListNode(sum); // append `sum`
tail = tail->next;
}
return dummy.next;
}
};
```

## Solution 2.

If we are asked to do it in-place.

```
// OJ: https://leetcode.com/problems/merge-nodes-in-between-zeros/
// Time: O(N)
// Space: O(1) as it's done in-place
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
ListNode dummy, *tail = &dummy;
while (head) {
if (head->val == 0) head = head->next;
if (!head) break;
auto node = head;
head = head->next;
while (head->val != 0) {
node->val += head->val;
head = head->next;
}
tail->next = node;
tail = tail->next;
node->next = nullptr;
}
return dummy.next;
}
};
```

If you are asked to add the code to free node:

```
// OJ: https://leetcode.com/problems/merge-nodes-in-between-zeros/
// Time: O(N)
// Space: O(1) as it's done in-place
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
ListNode dummy, *tail = &dummy;
while (head) {
if (head->val == 0) {
auto p = head;
head = head->next;
delete p;
}
if (!head) break;
auto node = head;
head = head->next;
while (head->val != 0) {
node->val += head->val;
auto p = head;
head = head->next;
delete p;
}
tail->next = node;
tail = tail->next;
node->next = nullptr;
}
return dummy.next;
}
};
```

## Discuss

https://leetcode.com/problems/merge-nodes-in-between-zeros/discuss/1784739/