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 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def mergeNodes(self, head: ListNode) -> ListNode:
8 dummy = ListNode(0)
9 tail = dummy
10 sum = 0
11 current = head.next
12
13 while current:
14 if current.val == 0:
15 tail.next = ListNode(sum)
16 tail = tail.next
17 sum = 0
18 else:
19 sum += current.val
20 current = current.next
21
22 return dummy.nextThe Python solution is straightforward and simple, making use of a dummy node to handle insertions. The sum is calculated by traversing from the head's next node (since head is guaranteed to be zero).
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
This recursive approach involves a helper function that traverses the linked list, accumulating values between zeros. When a zero is encountered, a node is created with the accumulated sum (if any) and the values reset for subsequent segments.