[数据结构与算法]430、扁平化多级双向链表

你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。

给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。

返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。

来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/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) {
        if(!head) return head;
        Node* cur = head;
        stack<Node*> stk;
        while(cur){
            if(cur->child){
                stk.push(cur);
                cur = cur->child;
            }
            else cur = cur->next;
        }
        while(!stk.empty()){
            Node* father = stk.top();
            stk.pop();
            Node* start = father->child;
            Node* end = father->child;
            while(end->next){
                end = end->next;
            }
            father->child = nullptr;
            start->prev = father;
            end->next = father->next;
            father->next = start;
            if(end->next) end->next->prev = end;
        }
        return head;
    }
};

解题方法二：递归

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/
class Solution {
public:
    Node* dfs(Node* head){
        Node* cur = head;
        while(!cur->child && cur->next){
            cur = cur->next;
        }
        if(cur->child){
            Node* NEXT = cur->next;
            cur->next = cur->child;
            cur->child->prev = cur;
            Node* end = dfs(cur->child);
            if(NEXT){
                end->next = NEXT;
                NEXT->prev = end;
            }
            cur->child = nullptr;
        }
        while(cur->next) cur = cur->next;
        return cur;
    }

    Node* flatten(Node* head) {
        if(!head) return head;
        Node* end = dfs(head); 
        return head;
    }
};