Flatten a multilevel doubly linked list leetcode solution

Nội dung chính Show

430. Flatten a Multilevel Doubly Linked List
Approach 1: Recursive
Approach 2: Iterative
Video liên quan

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

Top List List

Flatten a multilevel doubly linked list leetcode solution

430. Flatten a Multilevel Doubly Linked List

Approach 1: Recursive

Approach 2: Iterative

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội