430. 扁平化多級雙向鏈表

多級雙向鏈表中，除了指向下一個節點和前一個節點指針之外，它還有一個子鏈表指針，可能指向單獨的雙向鏈表。這些子列表也可能會有一個或多個自己的子項，依此類推，生成多級數據結構，如下面的示例所示。

給你位于列表第一級的頭節點，請你扁平化列表，使所有結點出現在單級雙鏈表中。

示例 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]
解釋：輸入的多級列表如下圖所示：1---2---NULL|3---NULL
示例 3：輸入：head = []
輸出：[]如何表示測試用例中的多級鏈表？以 示例 1 為例：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]
為了將每一級都序列化到一起，我們需要每一級中添加值為 null 的元素，以表示沒有節點連接到上一級的上級節點。[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
合并所有序列化結果，并去除末尾的 null 。[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

• 節點數目不超過 1000
• 1 <= Node.val <= 10^5

解題思路

類似于樹的遍歷，當遇到子節點的時候，優先遞歸進入子鏈表，并且遞歸返回的是子鏈表的末尾節點，那么我們就可以將子鏈表連接到第一級鏈表內部

代碼

/*
// Definition for a Node.
class Node {public int val;public Node prev;public Node next;public Node child;
};
*/class Solution {public Node flatten(Node head) {dfsFlatten(head);return head;}public Node dfsFlatten(Node head) {Node pre=null;while(head!=null){if(head.child!=null){Node next=head.next;Node tail=dfsFlatten(head.child);head.next=head.child;head.child.prev=head;head.child=null;if(next!=null){tail.next=next;next.prev=tail;}pre=tail;head=next;}else {pre=head;head=head.next;}}return pre;}
}