Skip to content

2181. Merge Nodes in Between Zeros 👍

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  ListNode* mergeNodes(ListNode* head) {
    if (head == nullptr)
      return nullptr;
    if (!head->next->val) {
      ListNode* node = new ListNode(head->val);
      node->next = mergeNodes(head->next->next);
      return node;
    }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public ListNode mergeNodes(ListNode head) {
    if (head == null)
      return null;
    if (head.next.val == 0) {
      ListNode node = new ListNode(head.val);
      node.next = mergeNodes(head.next.next);
      return node;
    }

    ListNode next = mergeNodes(head.next);
    next.val += head.val;
    return next;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def mergeNodes(self, head: ListNode | None) -> ListNode | None:
    if not head:
      return None
    if not head.next.val:
      node = ListNode(head.val)
      node.next = self.mergeNodes(head.next.next)
      return node

    next = self.mergeNodes(head.next)
    next.val += head.val
    return next

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  ListNode* mergeNodes(ListNode* head) {
    ListNode* curr = head->next;

    while (curr != nullptr) {
      ListNode* running = curr;
      int sum = 0;
      while (running->val > 0) {
        sum += running->val;
        running = running->next;
      }
      curr->val = sum;
      curr->next = running->next;
      curr = running->next;
    }

    return head->next;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public ListNode mergeNodes(ListNode head) {
    ListNode curr = head.next;

    while (curr != null) {
      ListNode running = curr;
      int sum = 0;
      while (running.val > 0) {
        sum += running.val;
        running = running.next;
      }
      curr.val = sum;
      curr.next = running.next;
      curr = running.next;
    }

    return head.next;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def mergeNodes(self, head: ListNode | None) -> ListNode | None:
    curr = head.next

    while curr:
      running = curr
      summ = 0
      while running.val > 0:
        summ += running.val
        running = running.next

      curr.val = summ
      curr.next = running.next
      curr = running.next

    return head.next