Sponsored
Sponsored
This approach involves traversing the linked list using a single pass while keeping a temporary sum of node values between consecutive zeros. We use a dummy node to help simplify edge cases related to list modifications.
Time Complexity: O(n), where n is the number of nodes in the linked list as we traverse the list only once.
Space Complexity: O(1), excluding the space needed for the new output list.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode() {}
5 ListNode(int val) { this.val = val; }
6 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7}
8
9public class Solution {
10 public ListNode mergeNodes(ListNode head) {
11 ListNode dummy = new ListNode(0);
12 ListNode tail = dummy;
13 int sum = 0;
14
15 for (ListNode node = head.next; node != null; node = node.next) {
16 if (node.val == 0) {
17 tail.next = new ListNode(sum);
18 tail = tail.next;
19 sum = 0;
20 } else {
21 sum += node.val;
22 }
23 }
24
25 return dummy.next;
26 }
27}The solution initializes a dummy node that helps to simplify the merging operation into the resultant list. The sum is calculated continuously between nodes with zero, adding a new node for the sum when a terminating zero is encountered.
Another approach we can take involves recursion to solve each segment between the zeros sequentially. Though iterative is usually preferred for this problem, recursion can offer a more functional programming perspective.
Time Complexity: O(n)
Space Complexity: O(n) due to recursive stack space
1public 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 {
private void RecursiveMerge(ListNode node, ref int sum, ref ListNode last) {
if (node == null) return;
if (node.val == 0 && sum > 0) {
last.next = new ListNode(sum);
last = last.next;
sum = 0;
} else if (node.val != 0) {
sum += node.val;
}
RecursiveMerge(node.next, ref sum, ref last);
}
public ListNode MergeNodes(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode last = dummy;
int sum = 0;
RecursiveMerge(head.next, ref sum, ref last);
return dummy.next;
}
}This C# solution uses recursion to accumulate node values between zeros. Using references allows persistence of sums and node additions throughout recursive calls.