2181. Merge Nodes in Between Zeros

You are given the head of a linked list, which contains a series of integers separated by 0‘s. The beginning and end of the linked list will have Node.val == 0.

For every two consecutive 0‘s, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0‘s.

Return the head of the modified linked list.

Example 1:

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation:
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 3 + 1 = 4.
- The sum of the nodes marked in red: 4 + 5 + 2 = 11.

Example 2:

Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation:
The above figure represents the given linked list. The modified list contains
- The sum of the nodes marked in green: 1 = 1.
- The sum of the nodes marked in red: 3 = 3.
- The sum of the nodes marked in yellow: 2 + 2 = 4.

Constraints:

• The number of nodes in the list is in the range [3, 2 * 105].
• 0 <= Node.val <= 1000
• There are no two consecutive nodes with Node.val == 0.
• The beginning and end of the linked list have Node.val == 0.

Approach 01:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        if (head == nullptr)
            return nullptr;
        
        if (!head->next || head->next->val == 0) {
            ListNode* node = new ListNode(head->val);
            node->next = mergeNodes(head->next ? head->next->next : nullptr);
            return node;
        }

        ListNode* next_node = mergeNodes(head->next);
        next_node->val += head->val;
        return next_node;
    }
};

class Solution:
    def mergeNodes(self, head: ListNode) -> ListNode:
        if not head:
            return None
        
        if not head.next or head.next.val == 0:
            node = ListNode(head.val)
            node.next = self.mergeNodes(head.next.next if head.next else None)
            return node
        
        next_node = self.mergeNodes(head.next)
        next_node.val += head.val
        return next_node

Time Complexity

• Traversal:

  Each node in the linked list is processed exactly once, resulting in a time complexity of \( O(n) \), where \( n \) is the number of nodes in the list.

• Recursive Calls:

  The function makes recursive calls to merge nodes, but each node is processed in constant time \( O(1) \) for checking conditions and updating pointers.

• Overall Time Complexity:

  The dominant factor is the traversal of the linked list, resulting in \( O(n) \) time complexity.

Space Complexity

• Recursive Stack:

  The space complexity is primarily determined by the recursive calls. In the worst case, where the linked list is skewed or all nodes satisfy the merge condition, the space complexity can go up to \( O(n) \) due to recursive function calls on the stack.

• Additional Space:

  Additional space used for creating new nodes and maintaining pointers is \( O(n) \) in the worst case, considering the recursive nature of the function.

• Overall Space Complexity:

  The space complexity is \( O(n) \) due to the recursive stack and additional space for creating new nodes.