Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

430. Flatten a Multilevel Doubly Linked List

Time: $O(n)$

Space: $O(n)$

			


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;
  }
};




			


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;
  }
}




			


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)