2181. Merge Nodes in Between Zeros

MediumView on LeetCode

Linked List Simulation

Time: O(n)

Space: O(1)

Intuition

Merge nodes between zeros. Scan linked list, accumulate sum between consecutive 0-value nodes.

Algorithm

1Skip initial 0. Accumulate sum until next 0 node. Create new node with sum. Continue.

Common Pitfalls

•Input guaranteed to start and end with 0. Build new list from sums between zeros.

2181.cs

// Approach: Single pass; accumulate values between 0-nodes and write sums into new list.
// Time: O(n) Space: O(1)

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public ListNode MergeNodes(ListNode head)
    {
        ListNode curr = head.next;

        while (curr != null)
        {
            ListNode running = curr;
            int sum = 0;
            while (running.val > 0)
            {
                sum += running.val;
                running = running.next;
            }

            curr.val = sum;
            curr.next = running.next;
            curr = curr.next;
        }

        return head.next;
    }
}

Was this solution helpful?