本期例題：LeetCode 206 - Reverse Linked List^[1](Easy)

反轉一個單鏈表。

示例：

• 輸入： 1->2->3->4->5->NULL

• 輸出： 5->4->3->2->1->NULL

反轉鏈表這道題是我在阿里的面試中遇到的題目。它本身也是單鏈表題目中非常典型的一道，不少題目的解法以反轉鏈表為基礎。這篇文章將會包含：

• 鏈表類題目的注意點
• 鏈表遍歷的基本框架
• 本期例題：反轉鏈表的解法
• 相關題目

鏈表類題目的注意點

在面試中涉及到的鏈表類題目，一定都是單鏈表。雖然實際中雙向鏈表使用較多，但單鏈表更適合作為面試題考察。

單鏈表這樣一個相對“簡陋”的數據結構，實際上就是為了考察面試者指針操作的基本功。很多題目需要修改指針鏈接，如果操作不當，會造成鏈表結點的丟失，或者出現錯誤的回路。

我們早在 C/C++ 編程課上就學過鏈表數據結構。你一定對各種鏈表的變體印象深刻，單鏈表、雙鏈表、循環鏈表……但是在面試中，請忘記你記得的各種花哨樣式，只使用最簡單的單鏈表操作。面試官很可能不希望看到你的各種“奇技淫巧”：

• 加入啞結點(即額外的鏈表頭結點)可以簡化插入操作，但面試官通常會要求你不要創建額外的鏈表結點，啞結點顯然也屬于額外的結點。
• 使用 C/C++ 的二級指針可以讓刪除結點的代碼非常精簡，但如果面試官對此不熟悉的話，會看得一頭霧水。

那么，如何才能簡潔明了地解決單鏈表問題呢？實際上很多鏈表題目都是類型化的，都可以歸結為鏈表的遍歷，以及在遍歷中做插入和刪除操作。我們可以使用鏈表遍歷的框架來解題。

鏈表遍歷的基本框架

單鏈表操作的本質難度在哪里？相比于雙向鏈表，單鏈表缺少了指向前一個結點的指針，所以在刪除結點時，還需要持有前一個結點的指針。這讓遍歷過程變得麻煩了許多。

比較容易想到的方法是將遍歷的指針指向“前一個結點”，刪除結點時使用 p.next = p.next.next。但這個方法會帶來一些心智負擔：

• 每次要查看的結點是 p.next，也就是下一個結點，別扭
• 循環終止條件不是 p == null 而是 p.next == null，容易出錯

不是很好的鏈表遍歷方式，有一定心智負擔

實際上，這就是單鏈表操作的復雜性所在。我們前面也否定了使用二級指針這樣的高級技巧來簡化操作的方法，那么，有沒有更簡單明了的遍歷方式呢？答案是有的。這里隆重推薦我一直在使用的鏈表遍歷框架：

當刪除鏈表結點時，既需要訪問當前結點，也需要訪問前一個結點。既然這樣，我們不妨使用兩個指針來遍歷鏈表，curr 指針指向當前結點，prev 指針指向前一個結點。這樣兩個指針的語義明確，也讓你寫出的代碼更易理解。

更好的鏈表遍歷框架，指針意義清晰易懂

用代碼寫出來，鏈表遍歷的框架是這樣的：

ListNode prev = null;
ListNode curr = head;
while (curr != null) {
// 進行操作，prev 表示前一個結點，curr 表示當前結點
if (prev == null) {
// curr 是頭結點時的操作
} else {
// curr 不是頭結點時的操作
}
prev = curr;
curr = curr.next;
}

在遍歷的過程中，需要一直維護 prev 是 curr 的前一個結點。curr 是循環中的主指針，整個循環的起始和終止條件都是圍繞 curr 進行的。prev 指針作為輔助指針，實際上就是記錄 curr 的上一個值。

在每一輪遍歷中，可以根據需要決定是否使用 prev 指針。注意 prev 可能為 null(此時 curr是頭結點)，在使用前需要先進行判斷。

使用兩個指針讓刪除結點非常容易：待刪除使用兩個指針讓刪除結點非常容易：已刪除

下面，我們看一看如何用這個鏈表遍歷的框架來解決本期的例題：反轉鏈表。

本期例題：反轉鏈表的解法

反轉鏈表的題目會有一個隱藏的要求：不能創建新的鏈表結點，只是在原有結點上修改鏈表指針。這樣的原地操作會比生成一個新的鏈表要難很多。

反轉鏈表的目標：鏈表結點不變，修改鏈表指針

Step 1 套用框架

這道題實際上就是一個典型的鏈表的遍歷-處理的操作，于是我們套用使用上面所講的鏈表遍歷框架。要反轉鏈表，實際上就是要反轉所有相鄰結點之間的指針。那么，整體的代碼框架應該是：

ListNode prev = null;
ListNode curr = head;
while (curr != null) {
// 反轉 prev 和 curr 之間的指針
prev = curr;
curr = curr.next;
}

可以看到，遍歷的框架已經將整體的思路架構了出來，我們知道按照如此的方式一定能遍歷到所有相鄰的結點對，也知道遍歷結束后循環一定能正常退出。接下來只需要關注每一步如何反轉結點之間的指針即可。

Step 2 寫好單步操作

單步操作是“反轉 prev 和 curr 之間的指針”。這里涉及到指針指向的改變，需要小心指針丟失的問題。在思考的時候，要考慮到和前一步、后一步的鏈接。

假設現在遍歷到了鏈表中部的某個結點。鏈表應該會分成兩個部分：prev 指針之前的一半鏈表已經進行了反轉；curr 之后的一半鏈表還是原先的順序。這次循環將讓 curr 的指針改為指向 prev，就將當前結點從后一半鏈表放進了前一半鏈表。

循環開始時，prev 和 curr 分別指向鏈表的前半部分和后半部分將當前結點放入前一半鏈表下一輪循環時，prev 和 curr 仍然分別指向鏈表的前半部分和后半部分

而頭結點的特殊情況是，全部鏈表都還未進行反轉，即前一半鏈表為空。顯然 curr.next 應當置為 null。

當前結點為頭結點時，前一半鏈表為空將 curr.next 置空，當前結點成為前一半鏈表的唯一結點

將單步操作放入代碼框架，我們就得到了一份初版的解題代碼：

ListNode prev = null;
ListNode curr = head;
while (curr != null) {
if (prev == null) {
curr.next = null;
} else {
curr.next = prev;
}
prev = curr;
curr = curr.next;
}

Step 3 細節處理

上面的代碼已經基本上比較完整了，但是還存在著明顯的錯誤，那就是存在指針丟失的問題。

我們使用 curr.next = prev 來反轉指針，但這會覆蓋掉 curr.next 本來存儲的值。丟掉這個指針之后，鏈表的后續結點就訪問不到了！

直接賦值 curr.next 是錯誤的，我們會丟掉指向下一個結點的指針

要解決指針丟失的問題也很簡單，使用一個臨時指針保存 curr 的下一個結點即可。如下圖所示：

使用臨時指針保存下一個結點，避免指針丟失問題

不過這樣一來，我們遍歷框架中更新指針的操作也要隨之進行微調。框架本來就不是一成不變的，需要根據實際題目靈活調整。

根據以上兩點的細節處理，我們修改得到完整版的代碼：

ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode cnext = curr.next;
if (prev == null) {
curr.next = null;
} else {
curr.next = prev;
}
prev = curr;
curr = cnext;
}
return prev;
}

上述代碼中，if 的兩個分支實際上可以優化合并，這里為了清晰起見仍然保留分支。

總結

總結起來，我們解決這一類單鏈表問題時，遵循的步驟是：

判斷問題是否為鏈表遍歷-修改，套用鏈表遍歷框架

思考單步操作，將代碼加入遍歷框架

檢查指針丟失等細節

有很多更復雜的鏈表題目都以反轉鏈表為基礎。下面列出了 LeetCode 上幾道相關的題目：

• LeetCode 203 - Remove Linked List Elements^[2] 是一道直白的鏈表刪除題目
• LeetCode 445 - Add Two Numbers II^[3] 以反轉鏈表為基礎解題
• LeetCode 92 - Reverse Linked List II^[4] 反轉部分鏈表

希望本文的講解能讓你在寫鏈表類題目時更得心應手。

參考資料

[1]

LeetCode 206 - Reverse Linked List: https://leetcode.com/problems/reverse-linked-list/

[2]

LeetCode 203 - Remove Linked List Elements: https://leetcode.com/problems/remove-linked-list-elements/

[3]

LeetCode 445 - Add Two Numbers II: https://leetcode.com/problems/add-two-numbers-ii/

[4]

LeetCode 92 - Reverse Linked List II: https://leetcode.com/problems/reverse-linked-list-ii/

---

由 五分鐘學算法 原班人馬打造的公眾號：圖解面試算法，現已正式上線！接下來我們將會在該公眾號上，為大家分享優質的算法解題思路，堅持每天一篇原創文章的輸出，視頻動畫制作不易，感興趣的小伙伴可以關注點贊一下哈！

總結

以上是生活随笔為你收集整理的假设以带头结点的循环链表表示队列_关于反转链表，看这一篇就够了！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。