[430. Flatten a Multilevel Doubly Linked List](https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/)

--- tags: leetcode --- # [430. Flatten a Multilevel Doubly Linked List](https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/) --- # My Solution ## The Key Idea for Solving This Coding Question Use DFS algorithm to find the tail of a flattened sublist. ## C++ Code ```cpp= /* // Definition for a Node. class Node { public: int val; Node* prev; Node* next; Node* child; }; */ class Solution { public: Node *flatten(Node *head) { dfs(head); return head; } private: // dfs returns the tail of the flattened linked list referred by head. Node *dfs(Node *head) { if (head == nullptr) { return nullptr; } if (head->child == nullptr) { // head has no child. if (head->next == nullptr) { // head has no child and next, so it is a tail. return head; } // head has no child but it has next. // Find the tail and return it. return dfs(head->next); } // head has child. if (head->next == nullptr) { // head has child but has no next. Node *childHead = head->child; Node *childTail = dfs(childHead); head->child = nullptr; head->next = childHead; childHead->prev = head; return childTail; } // head has both child and next. Node *headNext = head->next; Node *childHead = head->child; Node *childTail = dfs(childHead); head->child = nullptr; head->next = childHead; childHead->prev = head; childTail->next = headNext; headNext->prev = childTail; return dfs(headNext); } }; ``` ## Time Complexity $O(n)$ $n$ is the number of nodes in the multi-level list referred by `head`. ## Space Complexity $O(L)$ $L$ is the level of the mulit-level list referred by `head`. # Miscellaneous