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