LeetCode - Merge Nodes in Between Zeros

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/merge-nodes-in-between-zeros

Example 1:

Input: head = [0, 3, 1, 0, 4, 5, 2, 0]
Output: [4, 11]
Explanation:
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.

Example 2:

Input: head = [0, 1, 0, 3, 0, 2, 2, 0]
Output: [1, 3, 4]
Explanation:
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.

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 beginning and end of the linked list have Node.val == 0.

Explanation

We can solve the problem using two-pointers. According to the problem statement, the list start and end nodes are zero. We can set one pointer current to head->next and another pointer node to head.

We keep moving the pointer current to the next node until the node value is not equal to zero. While iterating, we keep adding the value of these nodes and assign it to the sum variable. We create a node with this sum value and assign node->next to the new ListNode.

We keep iterating the above approach till we reach the end of the linked list.

Let's check the algorithm for this approach.

- if head == NULL
  - return NULL

- set ListNode* current = head->next
      ListNode* node = head
      sum = 0

- loop while current
  - loop while current->val != 0
    - update sum = sum + current->val
    - update current = current->val
  - while end

  - set node->next = new ListNode(sum)
  - node = node->next

  - update sum = 0
  - current = current->next
- while end

- return head->next

The time complexity of the above approach is O(n), and the space complexity is O(1).

Let's check our algorithm in C++, Golang, and JavaScript.

C++ solution

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        if(head == NULL) {
            return NULL;
        }

        ListNode* current = head->next;
        ListNode* node = head;
        int sum = 0;

        while(current) {
            while(current->val != 0) {
                sum += current->val;
                current = current->next;
            }

            node->next = new ListNode(sum);
            node = node->next;

            sum = 0;
            current = current->next;
        }

        return head->next;
    }
};

Golang solution

func mergeNodes(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    current := head.Next
    node := head
    sum := 0

    for current != nil {
        for current.Val != 0 {
            sum += current.Val
            current = current.Next
        }

        node.Next = &ListNode{Val: sum}
        node = node.Next

        sum = 0
        current = current.Next
    }

    return head.Next
}

JavaScript solution

var mergeNodes = function(head) {
    if(head === null) {
        return null;
    }

    let current = head.next;
    let node = head;
    let sum = 0;

    while(current) {
        while(current.val != 0) {
            sum += current.val;
            current = current.next;
        }

        node.next = new ListNode(sum);
        node = node.next;

        sum = 0;
        current = current.next;
    }

    return head.next;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

Input: head -> [0, 3, 1, 0, 4, 5, 2, 0]

Step 1: if head == NULL
           head -> 0
           false

Step 2: current = head->next
                -> 3
        node = head
             -> 0
        sum = 0

Step 3: while current
          true

          while current->val != 0
            3 != 0
            true

            sum = sum + current->val
                = 0 + 3
                = 3

            current = current->next
                    -> 1

          while current->val != 0
            1 != 0
            true

            sum = sum + current->val
                = 3 + 1
                = 4

            current = current->next
                    -> 0

          while current->val != 0
            0 != 0
            false

          node->next = new ListNode(sum)
                     = new ListNode(4)

          node is head
          The list is now
          [0, 4]

          node = node->next
               -> 4

          sum = 0
          current = current->next
                  -> 4

Step 4: while current
          true

          while current->val != 0
            4 != 0
            true

            sum = sum + current->val
                = 0 + 4
                = 4

            current = current->next
                    -> 5

          while current->val != 0
            5 != 0
            true

            sum = sum + current->val
                = 4 + 5
                = 9

            current = current->next
                    -> 2

          while current->val != 0
            2 != 0
            true

            sum = sum + current->val
                = 9 + 2
                = 11

            current = current->next
                    -> 0

          while current->val != 0
            0 != 0
            false

          node->next = new ListNode(sum)
                     = new ListNode(11)

          node is head
          The list is now
          [0, 4, 11]

          node = node->next
               -> 11

          sum = 0
          current = current->next
                  -> nil

Step 5: while current
          false

Step 6: return head->next

We return the answer as [4, 11].