Merge Nodes in Between Zeros

medium linked list simulation

Problem

The head of a linked list starts with 0 and ends with 0, with no consecutive zeros in between. Merge the nodes between each pair of consecutive zeros into a single node whose value is the sum of those nodes. The zeros themselves are removed.

Inputhead = [0, 3, 1, 0, 4, 5, 2, 0]

Output[4, 11]

Sum 3+1=4 between the first two zeros; sum 4+5+2=11 between the next two.

list (must start and end with 0)

def merge_nodes(head):
    dummy = ListNode(0)
    tail = dummy
    cur = head.next
    s = 0
    while cur:
        if cur.val == 0:
            tail.next = ListNode(s)
            tail = tail.next
            s = 0
        else:
            s += cur.val
        cur = cur.next
    return dummy.next

function mergeNodes(head) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  let cur = head.next;
  let sum = 0;
  while (cur) {
    if (cur.val === 0) {
      tail.next = { val: sum, next: null };
      tail = tail.next;
      sum = 0;
    } else {
      sum += cur.val;
    }
    cur = cur.next;
  }
  return dummy.next;
}

class Solution {
    public ListNode mergeNodes(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        ListNode cur = head.next;
        int sum = 0;
        while (cur != null) {
            if (cur.val == 0) {
                tail.next = new ListNode(sum);
                tail = tail.next;
                sum = 0;
            } else {
                sum += cur.val;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

ListNode* mergeNodes(ListNode* head) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    ListNode* cur = head->next;
    int sum = 0;
    while (cur) {
        if (cur->val == 0) {
            tail->next = new ListNode(sum);
            tail = tail->next;
            sum = 0;
        } else {
            sum += cur->val;
        }
        cur = cur->next;
    }
    return dummy.next;
}

Explanation

The zeros in this list act like fences: every group of numbers sitting between two zeros should collapse into a single node holding their sum. So the whole job is just adding numbers up and dropping a new node every time we hit a zero.

We keep a running sum and a tail pointer on a dummy head. We start at head.next to skip the leading zero. For each node, if it is not zero we add its value to sum; if it is zero, that marks the end of a group, so we create a new node with the current sum, attach it, and reset sum to 0.

This works because the problem guarantees no two zeros are adjacent, so every zero (except the first) closes off exactly one non-empty group of numbers that we have been accumulating.

Example: [0, 3, 1, 0, 4, 5, 2, 0]. Skip the first 0. Add 3 then 1 (sum=4); hit a 0, so emit 4 and reset. Add 4, 5, 2 (sum=11); hit the final 0, emit 11. Result: [4, 11].

Because we touch each node once and only keep a couple of pointers, this runs in linear time with no extra bookkeeping beyond the output nodes themselves.

Time: O(n) Space: O(1) extra (excluding output)