Merge Nodes in Between Zeros

summary

• Given a linked list containing integers separated by 0's, merge every two consecutive 0's into a single node whose value is the sum of all the merged nodes.

approach

• This problem can be solved by iterating through the linked list and maintaining a running sum of nodes between two consecutive 0's
• When a 0 is encountered, a new node is created with the sum of the nodes between the previous 0 and the current 0, and the sum is reset to 0.

complexity

• O(n), where n is the number of nodes in the linked list, because each node is visited once.

explain

• The solution code first initializes a pointer to the second node in the list (after the first node) and a pointer to the new node that will be created
• It also initializes a sum variable to 0
• Then, it iterates through the list, adding each node's value to the sum if the current node is not a 0
• When a 0 is encountered, a new node is created with the sum of the nodes between the previous 0 and the current 0, and the sum is reset to 0
• The new node is linked to the previous node, and the previous node becomes the current node
• This process continues until the end of the list is reached, at which point the new node is returned as the head of the modified linked list.

Solution 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) {
        ListNode* answer = nullptr;
        ListNode* ptr2;
        int sum = 0;
        for (ListNode* ptr = head-> next; ptr != nullptr; ptr = ptr->next){
            if(ptr->val == 0){
                if (answer == nullptr){
                    answer = new ListNode(sum);
                    ptr2 = answer;
                } else {
                    ptr2->next = new ListNode(sum);
                    ptr2 = ptr2->next;
                }
                sum = 0;
            } else {
                sum += ptr->val;
            }
        }
        return answer;
    }
};