不可不會的反轉連結清單
反轉連結清單這題真的是面試非常喜歡考的了，這題看起來簡單，但是能用兩種方法一遍 bug free 也是不容易的，面試的時候可以篩下來一大批人，無論是對 junior 還是 senior 面試都很愛考。
今天就帶你梳理清楚思路，思路清楚了才能寫碼如有神。
題目
面試必備 | 不可不會的反轉連結清單
這是從力扣中文站上截下來的，但是這個輸出不太形象。
對連結清單的反轉，并不是要把它實際翻個個，隻是動一動 next 指針就好了。
什麼意思呢？
我們先看對數組進行反轉。
數組是一個實體上連續存儲的資料結構，反轉之後原來放 1 的位置就變成了放 5.
但是連結清單并不是，因為連結清單在實體上是不連續的，它的每個單元 ListNode 是通過 next 指針連接配接在一起的，而每個 ListNode 之間在記憶體裡并不一定是挨着的。
是以反轉連結清單，就不是非要把 1 的位置放 5，因為它們想在哪在哪。
那麼怎麼保證這個順序呢？
就是 next 指針。
沿着 next 指針的方向走下去，就是連結清單的順序。這也就保證了，隻要我們拿到了頭節點，就掌控了整個 LinkedList.
那麼題目中的例子，形象點是這個樣子滴：
也就是元素自己不用動，隻需要動動小指針，就是反轉了。
遞歸解法
遞歸的三步驟大家還記得嗎？
Base case + 拆解 + 組合
不記得的趕緊在公衆号内回複「遞歸」二字，擷取遞歸的入門篇詳解。
那麼我們來看這個題的：
base case:
當隻有一個 node，或者沒有 node 了呗，也就是
if(node == null || node.next == null) {
return node;
}
其實呢，隻剩一個 node 的時候嚴格來講并不是 base case，而是 corner case，
因為它本可以再 break down 到 node == null 的，但因為後面有對 node.next 的 dereference 操作，是以不能省略。
拆解：
遞歸的拆解就是把大問題，分解成小一點點的問題，直到 base case 可以傳回，進行第三步的組合。
那麼這裡就是
組合：
組合的意思是，假設我們能夠拿到小問題的解，那麼用小問題的解去構造大問題的解。
那麼這道題如何構造呢？
這裡很明顯，在 2 後面接上 1 就行了。
但是怎麼拿到 2 呢？
别忘了，原問題裡，此時還有 1 指向 2 呢～
也就是 node1.next = node2，
然後把 2 指向 1：node2.next = node1
合起來就是：node1.next.next = node1
思路清楚就不繞，看着覺得繞的就是沒想清楚哼～
代碼
遞歸的代碼寫起來都很簡潔：
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
時間複雜度
我們在「遞歸」這篇文章裡說過，遞歸的時間複雜度分析方法就是把遞歸樹畫出來，每個節點的時間加起來就行了。
這個遞歸樹是一個很簡單的單項連結清單，每個節點上做的就是那三行代碼，也就是「組合」做的事，即 O(1) 的時間，總共有 n 個節點，那麼總的時間就是 O(n).
空間複雜度
那看遞歸樹也很明顯了，每一層也就用了點小變量，是 O(1)，是以總的空間共是 O(n).
Iterative 解法
（誰能告訴我這個中文的專業說法。。
Iterative 的思路就是：
過一遍這個 Linked List，邊過邊把這個 node 的 next 指針指向前面那個 node，直到過完全部。
這樣說太抽象，面試時也是，直接過例子。
那也就是把 1 的 next 指針翻過來指向 NULL；
把 2 的 next 指針翻過來指向 1；
把 3 的 next 指針翻過來指向 2；
…
是以我們還需要一個變量來記錄目前 node 的前一個 node，不妨設為 prev.
同時呢，一旦我們把指針翻轉過去，後面的那個 node 就丢了有木有！是以還需要有個額外的變量事先記錄下後面的 node，設為 nxt，這樣才不至于走丢～
Step1.
翻轉箭頭：把 1 的 next 指針指向 NULL；
這樣子，同時我們也明确了，prev 的初始化應該是 NULL.
然後把這仨變量都移動到下一個位置：
Step2.
翻轉箭頭：把 2 的 next 指針指向 1，
Step3.
翻轉箭頭：把 3 的 next 指針指向 2，
再齊步走：
Step4.
再把 4 的反過來：
Step5.
再把 5 的 next 反過來：
但是因為我們的 while 循環包含了
「翻轉箭頭」+「三人行」
兩個步驟，是以還需要走完最後一個三人行，變成：
面試必備 | 不可不會的反轉連結清單
很多同學搞不清楚這個 while 循環的結束條件，其實很簡單，你就走個例子畫畫圖嘛！
那結束條件就是 curr = null 的時候，
最後傳回的是 prev.
好了，看代碼吧：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null) {
ListNode nxt = curr.next;
curr.next = prev; // 翻轉箭頭
prev = curr; //三人行
curr = nxt; //三人行
}
return prev;
}
}
時間複雜度
這裡的時間複雜度很明顯了，就是過了一遍這個連結清單，是以是 O(n).
空間複雜度
空間是 O(1).
高品質程式設計視訊：shangyepingtai.xin