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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode* next;
7};
8
9struct ListNode* mergeNodes(struct ListNode* head) {
10 struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
11 dummy->next = NULL;
12 struct ListNode* tail = dummy;
13
14 int sum = 0;
15 struct ListNode* iterator = head->next; // skip the first 0
16
17 while (iterator != NULL) {
18 if (iterator->val == 0) {
19 tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
20 tail = tail->next;
21 tail->val = sum;
22 tail->next = NULL;
23 sum = 0; // reset sum
24 } else {
25 sum += iterator->val;
26 }
27 iterator = iterator->next;
28 }
29
30 // Free the initial zero node
31 free(head);
32 return dummy->next; // return the new list, omitting the leading zero node
33}The solution uses a single traversal of the linked list. A dummy node is used to build the new list of merged node values. A temporary variable sum accumulates the values between two zeros. Once a zero is encountered, a new node with sum is appended to the resultant list, and sum is reset.
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>
2using 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.