430. Flatten a Multilevel Doubly Linked List
Approach 1: Recursive
- Time: $O[n]$
- Space: $O[n]$
C++JavaPython
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public:
Node* flatten[Node* head, Node* rest = nullptr] {
if [!head]
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
17 | 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
14 | 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]$
C++JavaPython
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]
tail = tail->next;
tail->next = cachedNext;
if [cachedNext]
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
|