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
1function
The recursive strategy in JavaScript divides the linked list into recursive calls and manages node summations through a helper function, similar to other languages.