Skip to content

430. Flatten a Multilevel Doubly Linked List 👍

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  Node* flatten(Node* head, Node* rest = nullptr) {
    if (head == nullptr)
      return rest;

    head->next = flatten(head->child, flatten(head->next, rest));
    if (head->next)
      head->next->prev = head;
    head->child = nullptr;
    return head;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public Node flatten(Node head) {
    return flatten(head, null);
  }

  private Node flatten(Node head, Node rest) {
    if (head == null)
      return rest;

    head.next = flatten(head.child, flatten(head.next, rest));
    if (head.next != null)
      head.next.prev = head;
    head.child = null;
    return head;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def flatten(self, head: 'Node') -> 'Node':
    def flatten(head: 'Node', rest: 'Node') -> 'Node':
      if not head:
        return rest

      head.next = flatten(head.child, flatten(head.next, rest))
      if head.next:
        head.next.prev = head
      head.child = None
      return head

    return flatten(head, None)

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:
  Node* flatten(Node* head) {
    for (Node* curr = head; curr; curr = curr->next)
      if (curr->child) {
        Node* cachedNext = curr->next;
        curr->next = curr->child;
        curr->child->prev = curr;
        curr->child = nullptr;
        Node* tail = curr->next;
        while (tail->next != nullptr)
          tail = tail->next;
        tail->next = cachedNext;
        if (cachedNext != nullptr)
          cachedNext->prev = tail;
      }

    return head;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public Node flatten(Node head) {
    for (Node curr = head; curr != null; curr = curr.next)
      if (curr.child != null) {
        Node cachedNext = curr.next;
        curr.next = curr.child;
        curr.child.prev = curr;
        curr.child = null;
        Node tail = curr.next;
        while (tail.next != null)
          tail = tail.next;
        tail.next = cachedNext;
        if (cachedNext != null)
          cachedNext.prev = tail;
      }

    return head;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def flatten(self, head: 'Node') -> 'Node':
    curr = head

    while curr:
      if curr.child:
        cachedNext = curr.next
        curr.next = curr.child
        curr.child.prev = curr
        curr.child = None
        tail = curr.next
        while tail.next:
          tail = tail.next
        tail.next = cachedNext
        if cachedNext:
          cachedNext.prev = tail
      curr = curr.next

    return head