2181. Merge Nodes in Between Zeros

Intuition

The problem requires merging nodes between zeros in a linked list and returning the modified list without zeros. The solution takes advantage of two pointers: slow to track the current node for merging and fast to traverse the list. By summing values between zeros and connecting nodes appropriately, we can achieve the desired result efficiently.

Approach: Two Pointers

Using two pointers, slow and fast, we can traverse the list while merging the values between zeros and adjusting the pointers to form the new linked list.

Explanation:

1. Initialization:
2. slow is initialized to the head of the list.
3. fast is initialized to the next node after head.
4. Traverse the List:
5. Iterate through the list using the fast pointer until fast->next is nullptr.
6. Sum Values and Adjust Pointers:
7. Summing Values:
   • If fast->val is not 0, add fast->val to slow->val.
8. Adjusting Pointers:
   • If fast->val is 0, it means we've reached the end of a segment to merge. Update slow->next to point to fast and move slow to fast.
9. Move the fast pointer to the next node.
10. Finalize the List:
11. Set slow->next to nullptr to ensure the new list terminates correctly.
12. Return the modified list starting from the head.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Code

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;

        while (fast->next) {
            if (fast->val != 0) {
                slow->val += fast->val;
            }
            else {
                slow->next = fast;
                slow = slow->next;
            }

            fast = fast->next;
        }

        slow->next = nullptr;
        return head;
    }
};