文章目錄
- 題目
- 題目決議
- 第一步：創建一個方法 pancake - 偏平化，來實作我們所有的操作，
- 第二步： 實作 pancake 方法
- 創建一個替身變數cur，來遍歷陣列，再創建一個 last 來記錄鏈表最終結果的最后一個節點位置，
- 接下來，我們就要遍歷鏈表，
- 進入回圈，此時，cur指向第一個節點位置，但是，正如我們前面所有說：我們無法確定 所有節點 child 為 null，還是補位null，所以我們就需要進行判斷 ： 此時cur指向的節點child 是否 為 null，
- 接下來，就是重點！ ( 遞回 )
- 然后就是正式 處理 開頭 和 收尾問題，
- 接下來就是沖上述操作
- 附上代碼
題目
?
題目決議
總的來說 ：就是遍歷一個鏈表，如果 child 為 null，則繼續遍歷下一個節點，但如果 child 不為 null，也就是說中止當前鏈表遍歷，遍歷 當前節點的child 所在鏈表，那么下一次遍歷的節點就是從child指向的節點開始（并插入到當前鏈表節點的next位置），直到遍歷完 child 所在的鏈表所有節點（前提是 child 所在的鏈表的所有節點 的child 都為 null，否則，按照前面說的，中止遍歷當前鏈表，優先遍歷完 child 所在鏈表），遍歷完后，繼續上部分還未遍歷完的鏈表（插入完child所在鏈表的所有節點，將其尾巴節點，接回原先鏈表中，繼續遍歷上部分鏈表未遍歷的部分），【遍歷的程序，包含鏈接，】
?
第一步：創建一個方法 pancake - 偏平化，來實作我們所有的操作，
?
第二步： 實作 pancake 方法
創建一個替身變數cur，來遍歷陣列，再創建一個 last 來記錄鏈表最終結果的最后一個節點位置，
因為我們無法確定該鏈表中所有節點 的 child 是否為 null，或者 child 所在鏈表的節點總數，所以一開始是無法確定 最后結果的節點位置，
?
接下來，我們就要遍歷鏈表，
?
進入回圈，此時，cur指向第一個節點位置，但是，正如我們前面所有說：我們無法確定 所有節點 child 為 null，還是補位null，所以我們就需要進行判斷 ： 此時cur指向的節點child 是否 為 null，
如果是，我們就需要記錄 cur 的 next 值，（當然提前創建一個變數來記錄）
方便 最后將 child 所在鏈表 的所有節點 插入 上部分鏈表時，收尾部分(將child所在鏈表的尾結點，上部分中斷的位子，進行鏈接，從而真正接入原先鏈表中)
?
接下來，就是重點！ ( 遞回 )
這里，我使用遞回思想，來看!
然后我們就需要去思考：這個遞回的終止條件是 cur,child == null，對不對？
來想一想：在遞回結束的時候，我們繼續遍歷當前遞回到child所在鏈表，直到遍歷完當前鏈表的所有節點，如果當前鏈表中的節點還存在 child，無非，就是在遞回一次，然后就跟我們現在一樣，就需遍歷當前鏈表，
在此程序 last 永遠指向都是 當前鏈表中最后一個節點，（也就是child 的 尾巴節點）
而我們，要將child 所在鏈表的節點全部插入進來，就需要最后一個節點的位置，
?
然后就是正式 處理 開頭 和 收尾問題，
?
接下來就是沖上述操作
你可以比較一下.
?
附上代碼
/*
// 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) {
pancake(head);
return head;
}
public Node pancake(Node node){
Node cur = node;
Node last = null;
while(cur != null){
Node next = cur.next;
if(cur.child != null){
Node childLast = pancake(cur.child);
next = cur.next;// 將next 更新到 目前 cur 的 next值，
// 解決善后問題后：我們是繼續遍歷 原先鏈表的
// 開頭鏈接
cur.next = cur.child;
cur.child.prev = cur;
if(next != null){// 如果next 為null，善后作業就沒必要了
childLast.next = next;
next.prev = childLast;
}
cur.child = null;
last = childLast;
}else{
last = cur;
}
cur = next;
}
return last;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/400540.html
標籤：java