Merge Nodes in Between Zeros

• Initialize a dummy node and a newTail pointer to build the result list.
• Initialize currentSum = 0.
• Iterate through the input list starting from head.next.
• If the current node's value is not 0, add it to currentSum.
• If the current node's value is 0, create a new node with currentSum, append it to the result list using newTail, and reset currentSum to 0.
• After the loop, return dummy.next.

We'll traverse the original list, keeping track of the sum of values in the current segment (between two zeros). A dummy node is used to simplify the construction of the new list. A tail pointer will track the end of the new list. We start iterating from the node after the initial zero. For each node, if its value is not zero, we add it to a running sum. When we encounter a zero, it signifies the end of a segment. We create a new node with the accumulated sum, append it to our new list, and reset the sum to zero for the next segment. This process continues until we've traversed the entire original list. The final result is the list starting from the dummy node's next pointer.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode mergeNodes(ListNode head) {13        ListNode dummy = new ListNode(0);14        ListNode newTail = dummy;15        ListNode current = head.next; // Skip the initial 016        int currentSum = 0;17 18        while (current != null) {19            if (current.val == 0) {20                // End of a segment21                if (currentSum > 0) {22                    newTail.next = new ListNode(currentSum);23                    newTail = newTail.next;24                }25                currentSum = 0; // Reset for the next segment26            } else {27                // Accumulate sum28                currentSum += current.val;29            }30            current = current.next;31        }32        return dummy.next;33    }34}

• Define a recursive function solve(node) that processes the list starting from a 0-node.
• Base Case: If node.next is null, return null.
• Move to the start of the segment: startNode = node.next.
• Iterate from startNode to find the next 0, calculating the sum of values.
• Update startNode.val with the calculated sum.
• Recursively call solve on the 0-node that ends the current segment: startNode.next = solve(zeroNode).
• Return startNode.
• The initial call is solve(head).

The main idea is to define a recursive function, say solve(node), that takes a 0-node as input and returns the head of the merged list for the part of the list that follows. The base case for the recursion is when the node after the input 0-node is null, which means we've reached the end of the list. In this case, we return null. In the recursive step, we first move to the node after the input 0-node. This is the start of a new segment. We can reuse this node to store the sum. We then iterate forward from this node to find the next 0, summing up the values along the way. Once we find the next 0, we update the value of the segment's starting node with the calculated sum. The next pointer of this updated node is then set to the result of a recursive call on the 0-node we just found. The initial call from the main function will be solve(head).

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode mergeNodes(ListNode head) {13        // The first node is a 0, so we start processing from it.14        // The recursive function will handle the segments.15        return solve(head);16    }17 18    private ListNode solve(ListNode node) {19        // 'node' is the 0 before the segment we need to process.20        node = node.next; // Move to the first node of the segment.21 22        // Base case: if we are at the end of the list (after the last 0).23        if (node == null) {24            return null;25        }26 27        // Find the sum of the current segment.28        ListNode runner = node;29        int sum = 0;30        while (runner.val != 0) {31            sum += runner.val;32            runner = runner.next;33        }34 35        // 'runner' is now at the next 0.36        // The start of the segment 'node' will be the new merged node.37        node.val = sum;38 39        // The next merged node is the result of the recursion on the rest of the list.40        node.next = solve(runner);41 42        return node;43    }44}

• Initialize modify = head to act as the tail of the result list, which is built starting from head.
• Initialize fast = head.next to traverse the list.
• Loop while fast is not null.
• Inside the loop, start a nested loop to find the next 0 and calculate the sum of the segment.
• Once the segment sum is calculated, store it in modify.next.val.
• Advance modify to modify.next.
• Advance fast past the 0 to the start of the next segment.
• After the main loop, set modify.next = null to correctly terminate the list.
• Return head.next.

We use two pointers. Let's call them modify and fast. The modify pointer will act as the tail of our new, condensed list. It will always point to the last valid merged node. We initialize it to head. The fast pointer will iterate through the original list to find segments and calculate their sums. We initialize it to head.next. The algorithm works by finding a segment (from one 0 to the next), calculating its sum, and then placing that sum into the node right after the one modify is pointing to. In each step of the main loop, fast moves forward, accumulating a sum until it hits a 0. Once a 0 is found, we have the sum for the segment. We update the value of modify.next with this sum. Then, we advance modify to modify.next, effectively extending our condensed list by one node. The fast pointer is then advanced to the node after the 0 it just found, to start processing the next segment. The loop continues until fast has traversed the entire list. Finally, we set modify.next = null to terminate the new list correctly. The result is head.next.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode mergeNodes(ListNode head) {13        // The first node (head) is a 0 and acts as a sentinel.14        // 'modify' will be the tail of the new list.15        ListNode modify = head;16        // 'fast' will traverse the list.17        ListNode fast = head.next;18 19        while (fast != null) {20            int sum = 0;21            // 'fast' is at the beginning of a segment.22            // Accumulate sum until the next 0.23            while (fast.val != 0) {24                sum += fast.val;25                fast = fast.next;26            }27 28            // 'fast' is now at a 0 node.29            // The node after 'modify' will store the sum.30            modify.next.val = sum;31            // Move 'modify' to this node.32            modify = modify.next;33 34            // Move 'fast' to the start of the next segment.35            fast = fast.next;36        }37        // Terminate the modified list.38        modify.next = null;39        40        // The new list starts after the sentinel 'head'.41        return head.next;42    }43}