• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
Node* flatten(Node* head, Node* rest = nullptr) {
return rest;

}
};
``````

## JAVA

``````class Solution {
public Node flatten(Node head) {
}

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

if (head.next != null)
}
}
``````

## Python

``````class Solution:
def flatten(self, head: 'Node') -> 'Node':
def flatten(head: 'Node', rest: 'Node') -> 'Node':
return rest

``````

• Time:O(n)
• Space:O(1)

## C++

``````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)
tail = tail->next;
tail->next = cachedNext;
if (cachedNext)
cachedNext->prev = tail;
}

}
};
``````

## JAVA

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

}
}
``````

## Python

``````class Solution:
def flatten(self, head: 'Node') -> 'Node':

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