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.
1function ListNode(val, next) {
2 this.val = (val===undefined ? 0 : val)
3 this.next = (next===undefined ? null : next)
4}
5
6function mergeNodes(head) {
7 let dummy = new ListNode(0);
8 let tail = dummy;
9 let sum = 0;
10 let current = head.next; // Skip the leading zero
11
12 while (current) {
13 if (current.val === 0) {
14 tail.next = new ListNode(sum);
15 tail = tail.next;
16 sum = 0;
17 } else {
18 sum += current.val;
19 }
20 current = current.next;
21 }
22
23 return dummy.next;
24}The JavaScript solution constructs a new linked list using a dummy node. Each segment sum is inserted as a new node by traversing nodes between zeros.
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
1
The recursive approach in Python illustrates a functional approach to breaking down the segments between zeros, using recursive calls to manage nodes and sums.