##### Welcome to Subscribe On Youtube

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

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;
if (head->val == 0) head = head->next; // skip leading 0
int sum = 0;
while (head->val != 0) { // sum numbers before the next 0
}
tail->next = new ListNode(sum); // append sum
tail = tail->next;
}
return dummy.next;
}
};

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

############

# 2181. Merge Nodes in Between Zeros
# https://leetcode.com/problems/merge-nodes-in-between-zeros/

# 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]:
curr = res = ListNode(-1)

s = 0

if head.val == 0:
curr.next = ListNode(s)
curr = curr.next
s = 0
else:

return res.next


• /**
* 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;
}
}

• /**
* 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.
* 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 cur = dummy;
let sum = 0;
if (head.val === 0 && sum !== 0) {
cur.next = new ListNode(sum);
cur = cur.next;
sum = 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(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(-1));
let mut cur = &mut dummy;
let mut sum = 0;
while let Some(node) = head {
if node.val == 0 && sum != 0 {
cur.next = Some(Box::new(ListNode::new(sum)));
cur = cur.as_mut().next.as_mut().unwrap();
sum = 0;
}
sum += node.val;
}
dummy.next.take()
}
}



## 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;
auto node = head;
while (head->val != 0) {
}
tail->next = node;
tail = tail->next;
node->next = nullptr;
}
return dummy.next;
}
};

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

############

# 2181. Merge Nodes in Between Zeros
# https://leetcode.com/problems/merge-nodes-in-between-zeros/

# 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]:
curr = res = ListNode(-1)

s = 0

if head.val == 0:
curr.next = ListNode(s)
curr = curr.next
s = 0
else:

return res.next


• /**
* 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;
}
}

• /**
* 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.
* 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 cur = dummy;
let sum = 0;
if (head.val === 0 && sum !== 0) {
cur.next = new ListNode(sum);
cur = cur.next;
sum = 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(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(-1));
let mut cur = &mut dummy;
let mut sum = 0;
while let Some(node) = head {
if node.val == 0 && sum != 0 {
cur.next = Some(Box::new(ListNode::new(sum)));
cur = cur.as_mut().next.as_mut().unwrap();
sum = 0;
}
sum += node.val;
}
dummy.next.take()
}
}



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;
if (head->val == 0) {
auto p = head;
delete p;
}
auto node = head;
while (head->val != 0) {
auto p = head;
delete p;
}
tail->next = node;
tail = tail->next;
node->next = nullptr;
}
return dummy.next;
}
};

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

############

# 2181. Merge Nodes in Between Zeros
# https://leetcode.com/problems/merge-nodes-in-between-zeros/

# 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]:
curr = res = ListNode(-1)

s = 0

if head.val == 0:
curr.next = ListNode(s)
curr = curr.next
s = 0
else:

return res.next


• /**
* 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;
}
}

• /**
* 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.
* 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 cur = dummy;
let sum = 0;
if (head.val === 0 && sum !== 0) {
cur.next = new ListNode(sum);
cur = cur.next;
sum = 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(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut dummy = Box::new(ListNode::new(-1));
let mut cur = &mut dummy;
let mut sum = 0;
while let Some(node) = head {
if node.val == 0 && sum != 0 {
cur.next = Some(Box::new(ListNode::new(sum)));
cur = cur.as_mut().next.as_mut().unwrap();
sum = 0;
}
sum += node.val;
}
dummy.next.take()
}
}



## Discuss

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