Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 430. Flatten a Multilevel Doubly Linked List

---

題目：


解答：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    Node* flatten(Node* head) {
        auto dfs = [&](this auto&& dfs, Node *n) -> Node* {
            Node *cur = n;
            Node *last = nullptr;

            while (cur) {
                Node *next = cur->next;

                if (cur->child) {
                    Node *chead = cur->child;
                    Node *ctail = dfs(chead);

                    cur->next = chead;
                    chead->prev = cur;
                    cur->child = nullptr;

                    if (next) {
                        ctail->next = next;
                        next->prev = ctail;
                    }

                    last = ctail;
                    cur = ctail;
                }
                else {
                    last = cur;
                }

                cur = cur->next;
            }

            return last;
        };

        dfs(head);
        return head;
    }
};