扁平化多級(jí)雙向鏈表
題目：多級(jí)雙向鏈表中，除了指向下一個(gè)節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)指針之外向图，它還有一個(gè)子鏈表指針泳秀，可能指向單獨(dú)的雙向鏈表。這些子列表也可能會(huì)有一個(gè)或多個(gè)自己的子項(xiàng)榄攀，依此類推嗜傅，生成多級(jí)數(shù)據(jù)結(jié)構(gòu)，如下面的示例所示檩赢。
給你位于列表第一級(jí)的頭節(jié)點(diǎn)吕嘀，請(qǐng)你扁平化列表，使所有結(jié)點(diǎn)出現(xiàn)在單級(jí)雙鏈表中贞瞒。
示例：
輸入：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]
解釋：
輸入的多級(jí)鏈表如下圖所示：
image
扁平化后的鏈表如下圖:
image
思路分析：
- 從當(dāng)前節(jié)點(diǎn)開(kāi)始處理偶房，如果沒(méi)有特殊邏輯，當(dāng)前節(jié)點(diǎn)往前運(yùn)動(dòng)（next）
- 如果遇到子節(jié)點(diǎn)憔狞，處理子節(jié)點(diǎn)邏輯蝴悉，子節(jié)點(diǎn)中如果無(wú)特殊邏輯，重復(fù)1.
- 返回鏈表頭head.
var flatten = function(head) {
let curNode = head;
while(curNode != null) {
if (curNode.child != null) {
// 如果含有子鏈表瘾敢，處理子鏈表
let childNode = curNode.child;
let nextChild = curNode.next;
// 當(dāng)前鏈表的下一個(gè)指向子鏈表
curNode.next = childNode;
// 當(dāng)前鏈表的子鏈表置為null
curNode.child = null;
// 子鏈表的上一個(gè)指向當(dāng)前鏈表
childNode.prev = curNode;
while (childNode.next != null) {
childNode = childNode.next;
}
childNode.next = nextChild;
if (nextChild != null) {
nextChild.prev = childNode;
}
}
curNode = curNode.next;
}
return head;
};
