Merge Nodes in Between Zeros

Medium
2022.

Merge Nodes in Between Zeros

MediumLinked ListSimulationAmazonGoogle

Merge Nodes in Between Zeros is a medium coding problem on simulation, asked in Amazon and Google interviews.

You are given the head of a linked list of integers separated by zeros: the list both starts and ends with a node of value 0, and no two 0 nodes are adjacent.

For every stretch of nodes lying between two consecutive 0s, replace the whole stretch by a single node whose value is the sum of the stretch. The resulting list contains no 0 nodes at all. Return its head.

Example 1

Input
head = [0,4,2,0,7,0,1,1,1,0]
Output
[6,7,3]
Explanation
The stretches are [4,2], [7] and [1,1,1], summing to 6, 7 and 3.

Example 2

Input
head = [0,5,0]
Output
[5]
Explanation
A single stretch holding one node.

Example 3

Input
head = [0,3,1,0,4,5,2,0]
Output
[4,11]
Explanation
The stretches [3,1] and [4,5,2] sum to 4 and 11.

Constraints

  • The number of nodes in the list is in the range [3, 2 * 10^5]
  • 0 <= Node.val <= 1000
  • There are no two consecutive nodes with Node.val == 0
  • The first and the last nodes have Node.val == 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * 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) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Merge Nodes in Between Zeros — Problem & Solution

Merge Nodes in Between Zeros solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Merge Nodes in Between Zeros is a medium coding problem on simulation, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Simulation
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the head of a linked list of integers separated by zeros: the list both starts and ends with a node of value 0, and no two 0 nodes are adjacent.

For every stretch of nodes lying between two consecutive 0s, replace the whole stretch by a single node whose value is the sum of the stretch. The resulting list contains no 0 nodes at all. Return its head.

Example 1

Input: head = [0,4,2,0,7,0,1,1,1,0]
Output: [6,7,3]
Explanation: The stretches are [4,2], [7] and [1,1,1], summing to 6, 7 and 3.

Example 2

Input: head = [0,5,0]
Output: [5]
Explanation: A single stretch holding one node.

Example 3

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: The stretches [3,1] and [4,5,2] sum to 4 and 11.

Constraints

  • The number of nodes in the list is in the range [3, 2 * 10^5]
  • 0 <= Node.val <= 1000
  • There are no two consecutive nodes with Node.val == 0
  • The first and the last nodes have Node.val == 0

Hints for Merge Nodes in Between Zeros

  1. Hint 1

    Every 0 after the first closes one stretch, so a single pass with a running sum is enough.

  2. Hint 2

    You do not need new nodes: the sums can be written into nodes the pass has already read.

  3. Hint 3

    There are fewer stretches than nodes read so far, so write each finished sum into the next node of the list from the front, and cut the list after the last one written.

How to solve Merge Nodes in Between Zeros

Scan once with a running sum, and every time a 0 closes a stretch write the sum into a node at the front of the list. The writer always trails the reader, so writing never destroys a value still to be read.

Approach

  1. Let write = head and last = null; start reading at head.next with sum = 0.
  2. For each node: if its value is 0, store sum in write, remember last = write, move write on and reset sum; otherwise add the value to sum.
  3. Cut the list after last (last.next = null) and return head.

Why it works

When the k-th stretch closes, the reader has passed at least 2k nodes (each stretch holds at least one non-zero node plus its closing zero), while the writer stands at node k - 1. So the writer only overwrites nodes that were read already.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The leading 0 opens the first stretch; it is not a separator that produces an empty sum.
  • Forgetting to cut the list after the last written sum leaves the old tail attached.

Reference solution

Python

from typing import Optional

def mergeNodes(head: Optional[ListNode]) -> Optional[ListNode]:
    write, last = head, None
    cur, s = head.next, 0
    while cur:
        if cur.val == 0:
            write.val = s
            last = write
            write = write.next
            s = 0
        else:
            s += cur.val
        cur = cur.next
    last.next = None
    return head

Java

public static ListNode mergeNodes(ListNode head) {
    ListNode write = head, last = null;
    int s = 0;
    for (ListNode cur = head.next; cur != null; cur = cur.next) {
        if (cur.val == 0) { write.val = s; last = write; write = write.next; s = 0; }
        else s += cur.val;
    }
    last.next = null;
    return head;
}

C++

ListNode* mergeNodes(ListNode* head) {
    ListNode *write = head, *last = nullptr;
    int s = 0;
    for (ListNode* cur = head->next; cur; cur = cur->next) {
        if (cur->val == 0) { write->val = s; last = write; write = write->next; s = 0; }
        else s += cur->val;
    }
    last->next = nullptr;
    return head;
}

JavaScript

var mergeNodes = function(head) {
    var write = head, last = null, s = 0;
    for (var cur = head.next; cur !== null; cur = cur.next) {
        if (cur.val === 0) { write.val = s; last = write; write = write.next; s = 0; }
        else s += cur.val;
    }
    last.next = null;
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 137 simulation problems · the whole catalogue