forked from KnowledgeCenterYoutube/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
430_Flatten_Multi_Level_Doubly_Linked_List
90 lines (82 loc) · 2.29 KB
/
430_Flatten_Multi_Level_Doubly_Linked_List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
Leetcode 430: Flatten a Multilevel Doubly Linked List
Deyailed video explanation: https://youtu.be/RIyPgR7AF7M
C++:
----
class Solution {
Node* flatten_rec(Node* head){
Node* curr = head;
Node* tail = head;
while(curr){
Node* child = curr->child;
Node* next = curr->next;
if(child){
Node* _tail = flatten_rec(child);
_tail->next = next;
if(next) next->prev = _tail;
curr->next = child;
curr->child = nullptr;
child->prev = curr;
curr = _tail;
}
else
curr = next;
if(curr) tail = curr;
}
return tail;
}
public:
Node* flatten(Node* head) {
if(head) flatten_rec(head);
return head;
}
};
Java:
----
class Solution {
private Node flatten_rec(Node head){
Node curr = head, tail = head;
while(curr != null){
Node child = curr.child;
Node next = curr.next;
if(child != null){
Node _tail = flatten_rec(child);
_tail.next = next;
if(next != null) next.prev = _tail;
curr.next = child;
curr.child = null;
child.prev = curr;
curr = _tail;
}
else
curr = next;
if(curr != null) tail = curr;
}
return tail;
}
public Node flatten(Node head) {
if(head != null) flatten_rec(head);
return head;
}
}
Python3:
-------
class Solution:
def flatten(self, head: 'Node') -> 'Node':
if head != None: self.flatten_rec(head)
return head
def flatten_rec(self, head):
curr, tail = head, head
while curr != None:
child, next = curr.child, curr.next
if child != None:
_tail = self.flatten_rec(child)
_tail.next = next
if next != None: next.prev = _tail
curr.next = child
curr.child = None
child.prev = curr
curr = _tail
else:
curr = next
if curr != None: tail = curr
return tail