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
1#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
void recursiveSum(ListNode* node, int& sum, ListNode*& tail) {
if (!node) return;
if (node->val == 0 && sum > 0) {
tail->next = new ListNode(sum);
tail = tail->next;
sum = 0;
} else if (node->val != 0) {
sum += node->val;
}
recursiveSum(node->next, sum, tail);
}
ListNode* mergeNodes(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
int sum = 0;
recursiveSum(head->next, sum, tail);
return dummy->next;
}Using recursion, each zero to zero segment is processed independently. The function adds to the list of nodes with the cumulative sum found in those segments.