430. 扁平化多級雙向鏈表

寫在前面：
最近事情比較多，馬上要準備期末考試了，現在是在複習。然後又有數據庫課設和計算機組成原理課設，好多事情要做，還有馬上就要考六級筆試了，每天都要刷英語題，但是做算法題我是一定會堅持下去的，希望大家可以和我一起努力，謝謝大家。
原題鏈接：
https://leetcode.cn/problems/...leetcode 430.扁平化多級雙向鏈表
題目描述：
你會得到一個雙鏈表，其中包含的節點有一個下一個指針、一個前一個指針和一個額外的子指針。這個子指針可能指向一個單獨的雙向鏈表，也包含這些特殊的節點。這些子列表可以有一個或多個自己的子列表，以此類推，以生成如下面的示例所示的多層數據結構給定鏈表的頭節點head,將鏈表扁平化，以便所有節點都出現在單層雙鏈表中。讓crr是一個帶有子列表的節點。子列表中的節點應該出現在扁平化列表中的curr之後和curr.next之前。返回扁平列表的had。列表中的節點必須將其所有子指針設置為NULL。
最開始題目我覺得有點難理解，要看好幾遍才可以理解，我建議你打開鏈接直接看leetcode裏面的題目描述，我這裏寫的不是很清楚。
示例：

做題思路

深度優先遍歷的思想，我這裏用的棧來寫深度優先遍歷，沒有用隊列，遇到一個節點cur，if(cur->child==NULL)cur=dfs(cur->next); else{ 遞歸搜索到孩子節點為頭節點的鏈表的尾部，將這幾個點連接好（這裏我用一張圖來表示）；}

注意：由於是雙向鏈表，要修改連接的地方有四個。然後t1,t2分別是是孩子鏈表上的頭和尾節點。

代碼c++版

class Solution {
public:
    Node* dfs(Node* now){
        if(now==NULL) return NULL;
        Node* ans=NULL;
        if(now->child==NULL){
            if(now->next==NULL) return now;
            ans=dfs(now->next);
        }
        else{
            Node* t1=now->child;
            Node* t2=dfs(now->child);
            Node* t3=now->next;
            now->child=NULL;
            now->next=t1;
            t1->prev=now;
            t2->next=t3;
            if(t3==NULL) return t2;
            else t3->prev=t2;
            ans=dfs(t3);
        }
        return ans;
    }
    Node* flatten(Node* head) {
        dfs(head);
        return head;
    }
};