2181. Merge Nodes in Between Zeros LeetCode Solution
In this guide, you will get 2181. Merge Nodes in Between Zeros LeetCode Solution with the best time and space complexity. The solution to Merge Nodes in Between Zeros problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2181. Merge Nodes in Between Zeros LeetCode Solution in C++
class Solution {
public:
ListNode* mergeNodes(ListNode* head) {
if (head == nullptr)
return nullptr;
if (!head->next->val) {
ListNode* node = new ListNode(head->val);
node->next = mergeNodes(head->next->next);
return node;
}
ListNode* next = mergeNodes(head->next);
next->val += head->val;
return next;
}
}; /* code provided by PROGIEZ */
2181. Merge Nodes in Between Zeros LeetCode Solution in Java
class Solution {
public ListNode mergeNodes(ListNode head) {
if (head == null)
return null;
if (head.next.val == 0) {
ListNode node = new ListNode(head.val);
node.next = mergeNodes(head.next.next);
return node;
}
ListNode next = mergeNodes(head.next);
next.val += head.val;
return next;
}
} // code provided by PROGIEZ
2181. Merge Nodes in Between Zeros LeetCode Solution in Python
class Solution:
def mergeNodes(self, head: ListNode | None) -> ListNode | None:
if not head:
return None
if not head.next.val:
node = ListNode(head.val)
node.next = self.mergeNodes(head.next.next)
return node
next = self.mergeNodes(head.next)
next.val += head.val
return next # code by PROGIEZ
