入門到進階:連結清單翻轉
接下來我們會重點看一下連結清單的翻轉，連結清單的翻轉可以衍生出很多的變形，是面試中非常熱門的考點，基本上考連結清單必考翻轉！是以掌握連結清單的翻轉是必修課！
什麼是連結清單的翻轉:給定連結清單 head–>4—>3–>2–>1，将其翻轉成 head–>1–>2–>3–>4 ，由于翻轉連結清單是如此常見，如此重要，是以我們分别詳細講解下如何用遞歸和非遞歸這兩種方式來解題.
- 遞歸翻轉
關于遞歸的文章之前寫了三篇，如果之前沒讀過的，強烈建議點選這裡檢視，總結了遞歸的常見解題套路,給出了遞歸解題的常見四步曲，如果看完對以下遞歸的解題套路會更加深刻，這裡不做贅述了，我們直接套遞歸的解題思路：
首先我們要檢視翻轉連結清單是否符合遞歸規律：問題可以分解成具有相同解決思路的子問題，子子問題…，直到最終的子問題再也無法分解。
要翻轉 head—>4—>3–>2–>1 連結清單，不考慮 head 結點，分析 4—>3–>2–>1，仔細觀察我們發現隻要先把 3–>2–>1 翻轉成 3<—-2<—-1，之後再把 3 指向 4 即可（如下圖示）
圖：翻轉連結清單主要三步驟
隻要按以上步驟定義好這個翻轉函數的功能即可， 這樣由于子問題與最初的問題具有相同的解決思路，拆分後的子問題持續調用這個翻轉函數即可達到目的。
注意看上面的步驟1，問題的規模是不是縮小了（如下圖），從翻轉整個連結清單變成了隻翻轉部分連結清單！問題與子問題都是從某個結點開始翻轉，具有相同的解決思路，另外當縮小到隻翻轉一個結點時，顯然是終止條件，符合遞歸的條件！之後的翻轉 3–>2–>1, 2–>1 持續調用這個定義好的遞歸函數即可！
既然符合遞歸的條件，那我們就可以套用
遞歸四步曲來解題了（注意翻轉之後 head 的後繼節點變了，需要重新設定！别忘了這一步）
1、定義遞歸函數,明确函數的功能 根據以上分析，這個遞歸函數的功能顯然是翻轉某個節點開始的連結清單，然後傳回新的頭結點
/**
* 翻轉結點 node 開始的連結清單
*/
public Node invertLinkedList(Node node) {
} 2、尋找遞推公式 上文中已經詳細畫出了翻轉連結清單的步驟，簡單總結一下遞推步驟如下
- 針對結點 node (值為 4), 先翻轉 node 之後的結點 invert(node->next) ,翻轉之後 4—>3—>2—>1 變成了 4—>3<—2<—1
- 再把 node 節點的下個節點（3）指向 node，node 的後繼節點設定為空（避免形成環），此時變成了 4<—3<—2<—1
- 傳回新的頭結點，因為此時新的頭節點從原來的 4 變成了 1，需要重新設定一下 head
3、将遞推公式代入第一步定義好的函數中，如下 (invertLinkedList)
/**
* 遞歸翻轉結點 node 開始的連結清單
*/
public Node invertLinkedList(Node node) {
if (node.next == null) {
return node;
}
// 步驟 1: 先翻轉 node 之後的連結清單
Node newHead = invertLinkedList(node.next);
// 步驟 2: 再把原 node 節點後繼結點的後繼結點指向 node，node 的後繼節點設定為空(防止形成環)
node.next.next = node;
node.next = null;
// 步驟 3: 傳回翻轉後的頭結點
return newHead;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
int[] arr = {4,3,2,1};
for (int i = 0; i < arr.length; i++) {
linkedList.addNode(arr[i]);
}
Node newHead = linkedList.invertLinkedList(linkedList.head.next);
// 翻轉後别忘了設定頭結點的後繼結點！
linkedList.head.next = newHead;
linkedList.printList(); // 列印 1，2，3，4
} 畫外音：翻轉後由于 head 的後繼結點變了，别忘了重新設定哦！
4、計算時間/空間複雜度 由于遞歸調用了 n 次 invertLinkedList 函數，是以時間複雜度顯然是 O(n), 空間複雜度呢，沒有用到額外的空間，但是由于遞歸調用了 n 次 invertLinkedList 函數，壓了 n 次棧，是以空間複雜度也是 O(n)。
遞歸一定要從函數的功能去了解，從函數的功能看，定義的遞歸函數清晰易懂，定義好了之後，由于問題與被拆分的子問題具有相同的解決思路，是以子問題隻要持續調用定義好的功能函數即可，切勿層層展開子問題，此乃遞歸常見的陷阱！仔細看函數的功能，其實就是按照下圖實作的。(對照着代碼看，是不是清晰易懂^_^)
- 非遞歸翻轉連結清單（疊代解法）
我們知道遞歸比較容易造成棧溢出，是以如果有其他時間/空間複雜度相近或更好的算法，應該優先選擇非遞歸的解法,那我們看看如何用疊代來翻轉連結清單，主要思路如下
步驟 1：定義兩個節點：pre, cur ，其中 cur 是 pre 的後繼結點，如果是首次定義， 需要把 pre 指向 cur 的指針去掉，否則由于之後連結清單翻轉，cur 會指向 pre， 就進行了一個環(如下)，這一點需要注意
步驟2：知道了 cur 和 pre,翻轉就容易了，把 cur 指向 pre 即可，之後把 cur 設定為 pre ，cur 的後繼結點設定為 cur 一直往前重複此步驟即可,完整動圖如下
注意：同遞歸翻轉一樣，疊代翻轉完了之後 head 的後繼結點從 4 變成了 1，記得重新設定一下。
知道了解題思路，實作代碼就容易多了，直接上代碼
/**
* 疊代翻轉
*/
public void iterationInvertLinkedList() {
// 步驟 1
Node pre = head;
Node cur = pre.getNext();
pre.setNext(null); // pre 是頭結點，避免翻轉連結清單後形成環
// 步驟 2
while (cur != null) {
/**
* 務必注意!!!：在 cur 指向 pre 之前一定要先保留 cur 的後繼結點，不然如果 cur 先指向 pre，之後就再也找不到後繼結點了
*/
Node next = cur.getNext();
cur.setNext(pre);
pre = cur;
cur = next;
}
// 此時 pre 指向的是原連結清單的尾結點，翻轉後即為連結清單 head 的後繼結點
head.next = pre;
} 用疊代的思路來做由于循環了 n 次，顯然時間複雜度為 O(n),另外由于沒有額外的空間使用，也未像遞歸那樣調用遞歸函數不斷壓棧，是以空間複雜度是 O(1),對比遞歸，顯然應該使用疊代的方式來處理！
花了這麼大的精力我們總算把翻轉連結清單給搞懂了，如果大家看了之後幾道翻轉連結清單的變形，會發現我們花了這麼大篇幅講解翻轉連結清單是值得的。
來源 | 五分鐘學算法
作者 | 程式員小吳