本期例題：LeetCode 206 - Reverse Linked List（Easy）
反轉(zhuǎn)一個單鏈表。
示例：
輸入： 1->2->3->4->5->NULL
輸出： 5->4->3->2->1->NULL
反轉(zhuǎn)鏈表這道題是我在阿里的面試中遇到的題目。它本身也是單鏈表題目中非常典型的一道，不少題目的解法以反轉(zhuǎn)鏈表為基礎(chǔ)。這篇文章將會包含：
- 鏈表類題目的注意點
- 鏈表遍歷的基本框架
- 本期例題：反轉(zhuǎn)鏈表的解法
- 相關(guān)題目
鏈表類題目的注意點
在面試中涉及到的鏈表類題目，一定都是單鏈表。雖然實際中雙向鏈表使用較多，但單鏈表更適合作為面試題考察。
單鏈表這樣一個相對“簡陋”的數(shù)據(jù)結(jié)構(gòu)，實際上就是為了考察面試者指針操作的基本功。很多題目需要修改指針鏈接，如果操作不當(dāng)，會造成鏈表結(jié)點的丟失，或者出現(xiàn)錯誤的回路。
我們早在 C/C++ 編程課上就學(xué)過鏈表數(shù)據(jù)結(jié)構(gòu)。你一定對各種鏈表的變體印象深刻，單鏈表、雙鏈表、循環(huán)鏈表……但是在面試中，請忘記你記得的各種花哨樣式，只使用最簡單的單鏈表操作。面試官很可能不希望看到你的各種“奇技淫巧”：
- 加入啞結(jié)點（即額外的鏈表頭結(jié)點）可以簡化插入操作，但面試官通常會要求你不要創(chuàng)建額外的鏈表結(jié)點，啞結(jié)點顯然也屬于額外的結(jié)點。
- 使用 C/C++ 的二級指針可以讓刪除結(jié)點的代碼非常精簡，但如果面試官對此不熟悉的話，會看得一頭霧水。
那么，如何才能簡潔明了地解決單鏈表問題呢？實際上很多鏈表題目都是類型化的，都可以歸結(jié)為鏈表的遍歷，以及在遍歷中做插入和刪除操作。我們可以使用鏈表遍歷的框架來解題。
鏈表遍歷的基本框架
單鏈表操作的本質(zhì)難度在哪里？相比于雙向鏈表，單鏈表缺少了指向前一個結(jié)點的指針，所以在刪除結(jié)點時，還需要持有前一個結(jié)點的指針。這讓遍歷過程變得麻煩了許多。
比較容易想到的方法是將遍歷的指針指向“前一個結(jié)點”，刪除結(jié)點時使用 p.next = p.next.next。但這個方法會帶來一些心智負擔(dān)：
- 每次要查看的結(jié)點是
p.next，也就是下一個結(jié)點，別扭 - 循環(huán)終止條件不是
p == null而是p.next == null，容易出錯
實際上，這就是單鏈表操作的復(fù)雜性所在。我們前面也否定了使用二級指針這樣的高級技巧來簡化操作的方法，那么，有沒有更簡單明了的遍歷方式呢？答案是有的。這里隆重推薦我一直在使用的鏈表遍歷框架：
當(dāng)刪除鏈表結(jié)點時，既需要訪問當(dāng)前結(jié)點，也需要訪問前一個結(jié)點。既然這樣，我們不妨使用兩個指針來遍歷鏈表，curr 指針指向當(dāng)前結(jié)點，prev 指針指向前一個結(jié)點。這樣兩個指針的語義明確，也讓你寫出的代碼更易理解。
用代碼寫出來，鏈表遍歷的框架是這樣的：
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
// 進行操作，prev 表示前一個結(jié)點，curr 表示當(dāng)前結(jié)點
if (prev == null) {
// curr 是頭結(jié)點時的操作
} else {
// curr 不是頭結(jié)點時的操作
}
prev = curr;
curr = curr.next;
}
在遍歷的過程中，需要一直維護 prev 是 curr 的前一個結(jié)點。curr 是循環(huán)中的主指針，整個循環(huán)的起始和終止條件都是圍繞 curr 進行的。prev 指針作為輔助指針，實際上就是記錄 curr 的上一個值。
在每一輪遍歷中，可以根據(jù)需要決定是否使用 prev 指針。注意 prev 可能為 null（此時 curr 是頭結(jié)點），在使用前需要先進行判斷。
下面，我們看一看如何用這個鏈表遍歷的框架來解決本期的例題：反轉(zhuǎn)鏈表。
本期例題：反轉(zhuǎn)鏈表的解法
反轉(zhuǎn)鏈表的題目會有一個隱藏的要求：不能創(chuàng)建新的鏈表結(jié)點，只是在原有結(jié)點上修改鏈表指針。這樣的原地操作會比生成一個新的鏈表要難很多。
Step 1 套用框架
這道題實際上就是一個典型的鏈表的遍歷-處理的操作，于是我們套用使用上面所講的鏈表遍歷框架。要反轉(zhuǎn)鏈表，實際上就是要反轉(zhuǎn)所有相鄰結(jié)點之間的指針。那么，整體的代碼框架應(yīng)該是：
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
// 反轉(zhuǎn) prev 和 curr 之間的指針
prev = curr;
curr = curr.next;
}
可以看到，遍歷的框架已經(jīng)將整體的思路架構(gòu)了出來，我們知道按照如此的方式一定能遍歷到所有相鄰的結(jié)點對，也知道遍歷結(jié)束后循環(huán)一定能正常退出。接下來只需要關(guān)注每一步如何反轉(zhuǎn)結(jié)點之間的指針即可。
Step 2 寫好單步操作
單步操作是“反轉(zhuǎn) prev 和 curr 之間的指針”。這里涉及到指針指向的改變，需要小心指針丟失的問題。在思考的時候，要考慮到和前一步、后一步的鏈接。
假設(shè)現(xiàn)在遍歷到了鏈表中部的某個結(jié)點。鏈表應(yīng)該會分成兩個部分： prev 指針之前的一半鏈表已經(jīng)進行了反轉(zhuǎn)；curr 之后的一半鏈表還是原先的順序。這次循環(huán)將讓 curr 的指針改為指向 prev，就將當(dāng)前結(jié)點從后一半鏈表放進了前一半鏈表。
而頭結(jié)點的特殊情況是，全部鏈表都還未進行反轉(zhuǎn)，即前一半鏈表為空。顯然 curr.next 應(yīng)當(dāng)置為 null。
將單步操作放入代碼框架，我們就得到了一份初版的解題代碼：
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 細節(jié)處理
上面的代碼已經(jīng)基本上比較完整了，但是還存在著明顯的錯誤，那就是存在指針丟失的問題。
我們使用 curr.next = prev 來反轉(zhuǎn)指針，但這會覆蓋掉 curr.next 本來存儲的值。丟掉這個指針之后，鏈表的后續(xù)結(jié)點就訪問不到了！
要解決指針丟失的問題也很簡單，使用一個臨時指針保存 curr 的下一個結(jié)點即可。如下圖所示：
不過這樣一來，我們遍歷框架中更新指針的操作也要隨之進行微調(diào)?？蚣鼙緛砭筒皇且怀刹蛔兊?，需要根據(jù)實際題目靈活調(diào)整。
根據(jù)以上兩點的細節(jié)處理，我們修改得到完整版的代碼：
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 的兩個分支實際上可以優(yōu)化合并，這里為了清晰起見仍然保留分支。
總結(jié)
總結(jié)起來，我們解決這一類單鏈表問題時，遵循的步驟是：
- 判斷問題是否為鏈表遍歷-修改，套用鏈表遍歷框架
- 思考單步操作，將代碼加入遍歷框架
- 檢查指針丟失等細節(jié)
有很多更復(fù)雜的鏈表題目都以反轉(zhuǎn)鏈表為基礎(chǔ)。下面列出了 LeetCode 上幾道相關(guān)的題目：
- 203 - Remove Linked List Elements 基礎(chǔ)的鏈表刪除題目
- 83 - Remove Duplicates from Sorted List 刪除鏈表中的重復(fù)結(jié)點
- 92 - Reverse Linked List II 反轉(zhuǎn)部分鏈表
希望本文的講解能讓你在寫鏈表類題目時更得心應(yīng)手。
