Merge Nodes in Between Zeros - Practice Coding Problems

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.

Input & Output

Example 1 — Basic Case

$ Input: head = [0,3,1,0,4,5,2,0]

› Output: [4,11]

💡 Note: Between first and second zero: 3+1=4. Between second and third zero: 4+5+2=11. Result is [4,11].

Example 2 — Single Segment

$ Input: head = [0,1,0,3,0,2,2,0]

› Output: [1,3,4]

💡 Note: Three segments: [1] gives 1, [3] gives 3, [2,2] gives 4. Result is [1,3,4].

Example 3 — Larger Values

$ Input: head = [0,10,20,0,5,15,0]

› Output: [30,20]

💡 Note: First segment: 10+20=30. Second segment: 5+15=20. Result is [30,20].

Constraints

The number of nodes in the list is in the range [3, 2 × 10⁵].
0 ≤ Node.val ≤ 1000
The beginning and end of the linked list have Node.val == 0.
There are no two consecutive nodes with Node.val == 0.

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list with zeros separating segments

Process

Sum values between consecutive zeros

Output

New list with merged segment sums

Key Takeaway

🎯 Key Insight: Transform zero nodes into sum nodes while traversing, eliminating the need for extra space

Asked in

M Microsoft 45 a Amazon 38 f Facebook 32 G Google 28

The key insight is to process segments between zeros in a single pass while building the result. The optimal approach uses in-place modification to transform zero nodes into sum nodes and skip intermediate nodes. Best approach is Single Pass In-Place: Time O(n), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass In-Place	O(n)	O(1)	Modify the original list in one pass without extra space
Two-Pass Approach	O(n)	O(k)	First pass to identify segments, second pass to create new nodes

Single Pass In-Place — Algorithm Steps

Start from first zero, track current sum
For each non-zero node, add to current sum
When hitting next zero, set previous zero's value to sum
Remove intermediate nodes by updating pointers

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Sum

Accumulate values between zeros

Update Zero

Replace zero with accumulated sum

Continue

Move to next segment

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head) {
    if (!head || !head->next) return NULL;
    
    struct ListNode* prevZero = head; // Points to the previous zero node
    struct ListNode* current = head->next;
    int currentSum = 0;
    
    while (current) {
        if (current->val == 0) {
            // Found next zero, update previous zero with sum
            prevZero->val = currentSum;
            prevZero->next = current;
            prevZero = current;
            currentSum = 0;
        } else {
            // Add to current segment sum
            currentSum += current->val;
        }
        current = current->next;
    }
    
    // Remove the trailing zero
    if (prevZero->next) {
        prevZero->next = NULL;
    }
    
    return head->val != 0 ? head : head->next;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array - simplified parser
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' || token[0] == '-') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    
    printf("[");
    struct ListNode* current = result;
    int first = 1;
    while (current) {
        if (!first) printf(",");
        printf("%d", current->val);
        first = 0;
        current = current->next;
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal through the linked list visiting each node once

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables for tracking, no extra data structures

✓ Linear Space

68.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass In-Place — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler