🌱 Keegan's Digital Garden

2181. Merge Nodes in Between Zeros

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- create a new linked list initialized to a nullptr
- interate through the original list, have a nested while loop that will progress the iteration between zeros, appending the values to a single node in the new list

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- Create a new dummy node to serve as the head of the new list.
- Use a pointer (`current`) to traverse the original list and accumulate the values between consecutive `0`s.
- Every time a `0` is encountered (after summing up the values)
	- create a new node with the accumulated sum and append it to the new list.
- Skip over the `0` and continue processing until the end of the list.
- Return the `next` of the dummy node as the head of the new list.

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(k) for the construction of the new linked list, where k is the number of non-zero segments

💻 Implementation of Solution

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        ListNode* dummy = new ListNode(0); // Dummy node for the new list
        ListNode* newTail = dummy;         // Pointer to build the new list
        ListNode* current = head->next;    // Skip the first zero
 
        while (current) {
            int sum = 0;
 
            // Accumulate values until the next zero
            while (current->val != 0) {
                sum += current->val;
                current = current->next;
            }
 
            // Add a new node with the accumulated sum to the new list
            newTail->next = new ListNode(sum);
            newTail = newTail->next;
 
            // Skip the zero and move to the next segment
            current = current->next;
        }
 
        return dummy->next; // Return the head of the new list
    }
};

Graph View