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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val=0, ListNode next=null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode MergeNodes(ListNode head) {
12 ListNode dummy = new ListNode(0);
13 ListNode tail = dummy;
14 int sum = 0;
15
16 for (ListNode node = head.next; node != null; node = node.next) {
17 if (node.val == 0) {
18 tail.next = new ListNode(sum);
19 tail = tail.next;
20 sum = 0;
21 } else {
22 sum += node.val;
23 }
24 }
25
26 return dummy.next;
27 }
28}The solution leverages a dummy node to streamline the final list construction with cumulative sum nodes added between zeros. This approach efficiently handles list transformations.
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.