阿竺 ·1. 前言
相對于各種復雜的二叉樹（例如平衡二叉樹、完美二叉樹），單鏈表的數(shù)據(jù)結(jié)構(gòu)簡單，只涉及到一個值和指針的操作，所以面試中經(jīng)常會出現(xiàn)需要手寫單鏈表的算法題。反轉(zhuǎn)鏈表應該是單鏈表中考察頻率最高的題目，題目看起來比較簡單，但是因為涉及的指針操作較多，要實現(xiàn)一遍 bug free 也不太容易。
2. 反轉(zhuǎn)鏈表
2.1 算法實現(xiàn)
面試官提問：如何反轉(zhuǎn)一個單鏈表？手寫實現(xiàn)一下源碼。
題目解析：
反轉(zhuǎn)鏈表是來源于算法網(wǎng)站LeetCode的經(jīng)典題目，題目鏈接：https://leetcode.com/problems/reverse-linked-list/。
反轉(zhuǎn)鏈表有多種解法：
（1）比較暴力（brute force）的方法是將鏈表的值放入一個有序數(shù)組，然后倒序從數(shù)組中取值，重新放入原有的鏈表。優(yōu)點是算法簡單，缺點是需要使用額外的數(shù)組空間，并且面試官一般不會接受這種不夠優(yōu)雅的算法；
（2）遞歸算法，遞歸本質(zhì)上也會使用額外的?？臻g（stack memory），優(yōu)點是算法簡潔，一般來說面試官也能接受遞歸；
（3）循環(huán)算法，使用多個指針在一次循環(huán)里改變鏈表順序，不會使用額外的空間，時間復雜度是O（N），這里只介紹這個方法。
循環(huán)算法中，我們需要借助三個指針，before 指針指向上一個操作節(jié)點，head 指針指向當前操作節(jié)點，next 指針指向下一個操作節(jié)點。算法可以拆分為兩個步驟：
（1）對于空鏈表以及只有單個節(jié)點的鏈表，直接返回鏈表本身，不需要進行反轉(zhuǎn)；
（2）對于普通鏈表，通過循環(huán)三個指針的操作實現(xiàn)鏈表反轉(zhuǎn)，我們使用Java實現(xiàn)反轉(zhuǎn)算法。
示例：
class Solution {
public ListNode reverseList(ListNode head) {
//1. 判斷邊界條件
if(head == null || head.next == null){
return head;
}
//2. 迭代反轉(zhuǎn)
ListNode dummy = head;
ListNode next, before = null;
while(head != null){
//3.1 反轉(zhuǎn)
next = head.next;
head.next = before;
//3.2 往后移動一位
before = head;
head = next;
}
return before;
}
}
為了校驗我們的算法是否有效，假設(shè)一個包含5個節(jié)點的鏈表，算法模擬的過程如下：
最開始給定的原始鏈表的結(jié)構(gòu)如下，其中黃色部分代表指針，藍色部分代表具體值：
經(jīng)過3.1步驟之后，鏈表的第一個節(jié)點被反轉(zhuǎn)，指向了before節(jié)點，此時before節(jié)點還是Null：
然后經(jīng)過3.2步驟后，我們把before、head、next的值都往后移動一位，第一個節(jié)點就完全實現(xiàn)了反轉(zhuǎn)：
接下來，我們重復上述步驟，直到 head 節(jié)點指向 Null ，即完成了整個鏈表的反轉(zhuǎn)，返回 before 節(jié)點就是新鏈表的頭節(jié)點。
2.2 細節(jié)考察
分析算法的時間復雜度和空間復雜度：上述循環(huán)算法，因為沒有使用遞歸，沒有使用額外的普通數(shù)組輔助存儲，只是使用了兩個臨時變量，所以空間復雜度為O（1）。因為通過單循環(huán)順序遍歷鏈表，所以時間復雜度為O（N）。
對于節(jié)點數(shù)量少于兩個的鏈表，需要提前返回原始鏈表，防止 NullPointerException空指針異常。
3. 小結(jié)
本章節(jié)介紹了單鏈表中最經(jīng)典的反轉(zhuǎn)鏈表問題，候選人從編寫算法源碼、通過小規(guī)模測試樣例驗證算法是否符合預期以及分析算法的時間和空間復雜度三個緯度入手，給出面試官滿意的答案。
2025 imooc.com All Rights Reserved |