medium Merge Nodes in Between Zeros

Problem Statement

You are given a head of the linked list where each node contains an integer. This list has segments separated by nodes with the value 0. The list starts and ends with a node containing 0.

For every pair of consecutive nodes with the value 0, merge all the nodes between them into a single node whose value is the sum of these nodes. The modified linked list should not include any 0 nodes.

Return the head of the updated linked list.

Examples

Example 1:

• Input: head = [0, 2, 3, 0, 4, 5, 0, 3, 0, 4, 0]
• Expected Output: [5, 9, 3, 4]
• Justification: The segments between 0s are [2, 3], [4, 5], [3], and [4]. Summing these segments gives 5, 9, 3, and 4, respectively.

Example 2:

• Input: head = [0, 1, 1, 1, 0, 2, 2, 0]
• Expected Output: [3, 4]
• Justification: The segments between 0s are [1, 1, 1] and [2, 2]. Summing these segments gives 3 and 4, respectively.

Example 3:

• Input: head = [0, 5, 0, 10, 15, 0]
• Expected Output: [5, 25]
• Justification: The segments between 0s are [5] and [10, 15]. Summing these segments gives 5 and 25, respectively.

Constraints:

• The number of nodes in the list is in the range [3, 2 * 10⁵].
• 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.

Solution

To solve this problem, you start by creating a helper or dummy node that will assist in managing the merging process. You then traverse the linked list, summing the values of nodes between two zeroes. When a zero is encountered, this sum is assigned to the current node. This approach is efficient because it ensures a single pass through the linked list, maintaining simplicity while managing the summing process within the nodes.

Step-by-step Algorithm

1. Initialize Helper Nodes:

   • Create a helperNode initialized to head.next to assist in merging nodes. This will be the node where we store the accumulated sums.
   • Set sumNode to helperNode to start the accumulation process. This node will traverse the list and accumulate the sums between zeros.

2. Loop Through the List:

   • While sumNode is not null:

     • This loop ensures we process all nodes in the list until we reach the end.

   1. Accumulate Sum Between Zeros:

      • Initialize accumulatedSum to 0:
        • This variable will keep track of the sum of node values between two zeros.
      • While sumNode.val is not 0:
        • This inner loop continues until we find a zero, indicating the end of the current segment.
        • Accumulate the value of sumNode into accumulatedSum:
          • Add the current node's value to accumulatedSum to keep a running total of the segment's values.
        • Move sumNode to the next node:
          • Advance to the next node in the list to continue accumulation.

   2. Update the Helper Node with Accumulated Sum:

      • Assign accumulatedSum to helperNode.val:
        • Store the accumulated sum in the current helperNode. This step replaces the value of the helper node with the sum of the segment, effectively merging the nodes.

   3. Move to the Next Segment:

      • Move sumNode to the next node after the zero:
        • Skip the zero node and move to the start of the next segment.
      • Update helperNode.next to sumNode:
        • Link the current helper node to the start of the next segment.
      • Move helperNode to helperNode.next:
        • Advance helperNode to the next node where the next accumulated sum will be stored.

3. Return the Result:

   • Return head.next which points to the merged list starting from the first accumulated sum. This skips the initial zero node in the original list.

Algorithm Walkthrough

Using the input [0, 2, 3, 0, 4, 5, 0, 3, 0, 4, 0]:

1. Initialization:

   • helperNode points to the node with value 2 (the first non-zero node).
   • sumNode also points to the node with value 2.

2. First Segment:

   • accumulatedSum is initialized to 0.
   • Traverse nodes 2 and 3:
     • accumulatedSum becomes 2 after the first node.
     • accumulatedSum becomes 5 after the second node.
   • sumNode reaches the node with value 0.
   • Set helperNode.val to 5.
   • Move sumNode to the next node (4).
   • Set helperNode.next to sumNode.
   • Move helperNode to the node with value 4.

3. Second Segment:

   • accumulatedSum is reset to 0.
   • Traverse nodes 4 and 5:
     • accumulatedSum becomes 4 after the first node.
     • accumulatedSum becomes 9 after the second node.
   • sumNode reaches the node with value 0.
   • Set helperNode.val to 9.
   • Move sumNode to the next node (3).
   • Set helperNode.next to sumNode.
   • Move helperNode to the node with value 3.

4. Third Segment:

   • accumulatedSum is reset to 0.
   • Traverse the node 3:
     • accumulatedSum becomes 3.
   • sumNode reaches the node with value 0.
   • Set helperNode.val to 3.
   • Move sumNode to the next node (4).
   • Set helperNode.next to sumNode.
   • Move helperNode to the node with value 4.

5. Fourth Segment:

   • accumulatedSum is reset to 0.
   • Traverse the node 4:
     • accumulatedSum becomes 4.
   • sumNode reaches the node with value 0.
   • Set helperNode.val to 4.
   • Move sumNode to the next node (null).
   • Set helperNode.next to null.

6. End of List:

   • sumNode is null, so the traversal ends.

7. Return the Result:

   • Return the node following the initial 0 node.
   • The resulting linked list is [5, 9, 3, 4].

Code

// class ListNode {
//     int val;
//     ListNode next;
//     ListNode(int val) { this.val = val; }
// }

public class Solution {

  public ListNode mergeNodes(ListNode head) {
    // Create a placeholder node to assist in merging
    ListNode helperNode = head.next;
    ListNode sumNode = helperNode;

    while (sumNode != null) {
      int accumulatedSum = 0;
      // Accumulate sum of nodes between zeros
      while (sumNode.val != 0) {
        accumulatedSum += sumNode.val;
        sumNode = sumNode.next;
      }

      // Assign the accumulated sum to the current node's value
      helperNode.val = accumulatedSum;
      // Move sumNode to the first non-zero value of the next segment
      sumNode = sumNode.next;
      // Move helperNode also to this node
      helperNode.next = sumNode;
      helperNode = helperNode.next;
    }
    return head.next;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Test Example 1
    ListNode head1 = new ListNode(0);
    head1.next = new ListNode(2);
    head1.next.next = new ListNode(3);
    head1.next.next.next = new ListNode(0);
    head1.next.next.next.next = new ListNode(4);
    head1.next.next.next.next.next = new ListNode(5);
    head1.next.next.next.next.next.next = new ListNode(0);
    head1.next.next.next.next.next.next.next = new ListNode(3);
    head1.next.next.next.next.next.next.next.next = new ListNode(0);
    head1.next.next.next.next.next.next.next.next.next = new ListNode(4);
    head1.next.next.next.next.next.next.next.next.next.next = new ListNode(0);
    ListNode result1 = sol.mergeNodes(head1);
    while (result1 != null) {
      System.out.print(result1.val + " ");
      result1 = result1.next;
    }
    System.out.println(" ");

    // Test Example 2
    ListNode head2 = new ListNode(0);
    head2.next = new ListNode(1);
    head2.next.next = new ListNode(1);
    head2.next.next.next = new ListNode(1);
    head2.next.next.next.next = new ListNode(0);
    head2.next.next.next.next.next = new ListNode(2);
    head2.next.next.next.next.next.next = new ListNode(2);
    head2.next.next.next.next.next.next.next = new ListNode(0);
    ListNode result2 = sol.mergeNodes(head2);
    while (result2 != null) {
      System.out.print(result2.val + " ");
      result2 = result2.next;
    }
    System.out.println(" ");

    // Test Example 3
    ListNode head3 = new ListNode(0);
    head3.next = new ListNode(5);
    head3.next.next = new ListNode(0);
    head3.next.next.next = new ListNode(10);
    head3.next.next.next.next = new ListNode(15);
    head3.next.next.next.next.next = new ListNode(0);
    ListNode result3 = sol.mergeNodes(head3);
    while (result3 != null) {
      System.out.print(result3.val + " ");
      result3 = result3.next;
    }
    System.out.println(" ");
  }
}

Complexity Analysis

• Time Complexity: The time complexity of the solution is , where n is the number of nodes in the linked list. This is because we traverse each node exactly once to compute the sums and adjust the links.

• Space Complexity: The space complexity is . We are not using any extra data structures that grow with the size of the input. We only use a few pointers and variables for the summing and linking process.