Merge Nodes in Between Zeros

Leetcode 2181: Merge Nodes in Between Zeros

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:

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.

Soure: Leetcode 2181. Merge Nodes in Between Zeros

Solution

Analysis

Let’s take an input list like [0, 2, 7, 0, 5, 1, 0].

We can solve this problem with additional two pointers. Let’s assume the head pointer of the given linked list is the owner or boss of the linked list. He employed a manager whose name is local_node. He also hired a worker named temp to work under local_node. As a first quick step, we can move head to point to its next node since the first node is always zero. We will do this forward movement of head before assigning local_node and temp to point head.

Now, after head pointed to its next node, ocal_node and temp are created and they assigned value of head. So, at this point head, local_node and temp are all pointing to the second node of the linked list as the image below.

The job of temp node is to move forward and sum up all the non zero values and keep the sum in a variable sum (we used variable name _sum in the Python code to avoid conflict with Python’s built-in sum function). After traversing and summing, when temp points to the next zero node, local_head takes the sum and update itself. See the next image to understand this.

Then it updates its next pointer to point to the next pointer of temp as shown in the image below.

Remember, temp is now pointing to a zero, the next pointer of temp is pointing to either NULL or a non-zero element. At this point, temp will move forward as below image.

All we need now is to move local_head forward. Since local_hed‘s next was pointing to the next of temp‘s previous position (where temp is pointing now), at this stage both of them will point to the same node. Finally, sum will be reinitialized to zero. Below image shows the final stage after one merge happens.

You see here we didn’t use any additional space to store the entire linked list. Nodes that are not used anymore, for example, 7 and 0 will remain as dangling nodes. From the steps so far, we can see that, head is still pointing to a node which is the merge result of non-zero elements. If we follow these steps to the entire linked list, we will get the output list = [9, 6].

Below are codes that explains the process. If you find it difficult to understand the algorithm, please try to think about it for some time, come back to this post and re-read the explanation. Hope that will help 🙂

C++ code

/**
 * 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) {
        //First value is zero, so we can omit that
        if(head->val==0)
            head = head->next;
        
        ListNode* local_head = head; // local_head will contain result(sum) of merged nodes
        ListNode* temp = head; // temp will help to traverse the linked list
        int sum = 0;
        
        while(temp != NULL){
            if(temp->val != 0){ 
                sum += temp->val; //node is not 0, so we sum up
                temp = temp->next;//and move forward
            }
            else{
                local_head->val = sum; //we have the sum upto this point, we now update local_head's value
                local_head->next = temp->next; //local_head no need to point to its original next element, it will point to the next of temp now
                temp = temp->next;
                local_head = local_head->next;
                sum = 0;
            }
        }
        
        return head;
    }
};

Java code

class Solution {
    public ListNode mergeNodes(ListNode head) {
        //First value is zero, so we can omit that
        if(head.val==0)
            head = head.next;
        
        ListNode local_head = head; // local_head will contain result(sum) of merged nodes
        ListNode temp = head; // temp will help to traverse the linked list
        int sum = 0;
        
        while(temp != null){
            if(temp.val != 0){ 
                sum += temp.val; //node is not 0, so we sum up
                temp = temp.next;//and move forward
            }
            else{
                local_head.val = sum; //we have the sum upto this point, we now update final_head's value
                local_head.next = temp.next; //final_head no need to point to its original next element, it will point to the next of temp now
                temp = temp.next;
                local_head = local_head.next;
                sum = 0;
            }
        }
        
        return head;
    }
}

Python code

# 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]:
        if head.val == 0:
            head = head.next
        local_head = head #local_head will contain result(sum) of merged nodes
        temp = head       #temp will help to traverse the linked list
        _sum = 0
        
        while temp is not None:
            if temp.val is not 0:
                _sum += temp.val #node is not 0, so we sum up
                temp = temp.next #and move forward
            else:
                local_head.val = _sum #we have the sum upto this point, we now update local_head's value
                local_head.next = temp.next #local_head now doesn't need to point to its original next element, it will point to the next of temp now
                temp = temp.next #move temp forward
                local_head = local_head.next #move local_head forward
                _sum = 0 #reset _sum to 0
        
        return head
        

Javascript code

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var mergeNodes = function(head) {
    //First value is zero, so we can omit that
        if(head.val==0)
            head = head.next;
        
        let local_head = head; // local_head will contain result(sum) of merged nodes
        let temp = head; // temp will help to traverse the linked list
        let sum = 0;
        
        while(temp != null){
            if(temp.val != 0){ 
                sum += temp.val; //node is not 0, so we sum up
                temp = temp.next;//and move forward
            }
            else{
                local_head.val = sum; //we have the sum upto this point, we now update final_head's value
                local_head.next = temp.next; //final_head no need to point to its original next element, it will point to the next of temp now
                temp = temp.next;
                local_head = local_head.next;
                sum = 0;
            }
        }
        
        return head;
};

Time and Space Complexity

Time – O(N), since we are traversing the entire list

Space – O(1), we are not using any extra space that will grow proportionate to the input size.

Conclusion

Hope this post helped you understand the solution of Leetcode 2181: Merge Nodes in Between Zeros. If you like it or hate it, please post some comments so that we can improve our writing or get motivation! Happy Coding!

Bonus – System Design!

ByteByteGo is by far the best system design resource found on the internet. They are growing like crazy!

We suggest you checkout their course if you really want to dive deep in system design and want to have a killer interview!

Here is the link: ByteByteGo!

Disclaimer: this is a genuine suggestion, but we have some interest too! We get commission if you buy their course. However, there are other courses online which we do not promote. Because we promote only things that are the best in our opinion and those we really feel will be helpful for you.