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 <iostream>
2using namespace std;
3
4struct ListNode {
5 int val;
6 ListNode* next;
7 ListNode() : val(0), next(nullptr) {}
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode* next) : val(x), next(next) {}
10};
11
12ListNode* mergeNodes(ListNode* head) {
13 ListNode* dummy = new ListNode();
14 ListNode* tail = dummy;
15 int sum = 0;
16
17 for (ListNode* ptr = head->next; ptr != nullptr; ptr = ptr->next) {
18 if (ptr->val == 0) {
19 tail->next = new ListNode(sum);
20 tail = tail->next;
21 sum = 0;
22 } else {
23 sum += ptr->val;
24 }
25 }
26
27 return dummy->next;
28}The structure follows a similar pattern to the C solution. A dummy node is used to start the result list, and we append new nodes with summed values whenever a zero is encountered. sum temporarily holds the total of values 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 strategy in JavaScript divides the linked list into recursive calls and manages node summations through a helper function, similar to other languages.