主題
題目連結：
題目意譯：
你被給定一個雙向連結串列（Doubly Linked List），其節點包含著一個 next（下一個）指標、一個 previous（上一個）指標以及一個額外的 child（小孩）指標。這個 child 指標可能會或不會指向另一個獨立的雙向連結串列，其同樣也包含著這些特別的節點之架構。這些小孩串列可能自己又被再包含一個或多個小孩，以此類推，因此產生出了一個如下面的圖所示的多層次資料結構。
給定串列第一層的開頭節點 head，將該串列整個攤平使得每個節點都出現於一個單一一層的雙向連結串列。令 curr 為有著一個小孩串列的一個節點。則在攤平後的串列中，小孩串列中的節點應出現於 curr 之後以及 curr.next 之前。
回傳攤平後的串列之開頭節點 head。串列中的每個節點之 child 指標都應設為空（Null）。
限制：
節點數不超過 1000 個。
1 ≦ Node.val ≦ 10 ^ 5
在測試資料是如何表示多層次連結串列的：
我們以下面的範例一的多層次連結串列為例：
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
每一層的序列化為以下：
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
為了將每一層一起序列化，我們將會在每一層加上一些「空」來強調沒有節點連結到前一層的節點。序列化現在變為：
[1, 2, 3, 4, 5, 6, null]
|
[null, null, 7, 8, 9, 10, null]
|
[ null, 11, 12, null]
將每一層的序列化合在一起並移除掉末尾的「空」則我們將得到：
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
範例測資：
範例 1：
輸入： head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
輸出： [1,2,3,7,8,11,12,9,10,4,5,6]
解釋： 輸入中的多層次連結串列於上圖所示。
將該多層次連結串列攤平後將變為：
範例 2：
輸入： head = [1,2,null,3]
輸出： [1,3,2]
解釋： 輸入中的多層次連結串列於上圖所示。
將該多層次連結串列攤平後將變為：
範例 3：
輸入： head = []
輸出： []
解釋： 輸入可以為空串列。
解題思維：
掃過整個串列（假設現在在節點 i），先判斷 i 的 child 指標是否指向另一串列（即判斷是否為空）。
如果有指向另一個串列則我們直接遞迴地攤平這一個串列，其中我們需要記錄其攤平後的結尾節點。然後在這一個串列攤平並回到原本這一層後，從剛剛記錄的結尾節點後面再繼續接著節點 i 後面的節點們。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
