上周三晚上十一點(diǎn)多一個(gè)剛轉(zhuǎn)方向?qū)W C 的朋友給我發(fā)消息說 Reverse Linked List 這道題他看了三遍題解合上編輯器還是寫不對指針一改就斷鏈。這事兒我太熟了——鏈表反轉(zhuǎn)是算法題里少見的「代碼不到十行、坑卻有一籮筐」的典型難度標(biāo)記 Easy但真正能一次性寫對、并且講清楚每一行指針為什么這么動(dòng)的人比例并不高。這篇記錄來自我自己刷 C 算法題時(shí)留下的筆記圍繞 Reverse Linked List反轉(zhuǎn)鏈表這道 Easy 題展開。我會(huì)把迭代、遞歸、頭插法三種寫法逐行拆開把本地自測環(huán)境的搭建、編譯命令、常見報(bào)錯(cuò)的排查過程都寫進(jìn)去再順手把它延伸出去的區(qū)間反轉(zhuǎn)、K 個(gè)一組反轉(zhuǎn)一起串一遍。它不是給判題機(jī)交作業(yè)用的答案而是一份能落地復(fù)現(xiàn)的工程筆記你在 VSCode 里新建一個(gè) .cpp 文件照著敲一遍就能在本機(jī)跑出結(jié)果、看到每一輪指針的變化。適合誰看如果你剛學(xué)完 C 的結(jié)構(gòu)體和指針還沒真正搞明白「指針的指針在什么位置被改寫」這篇能幫你把地基夯一遍如果你已經(jīng)能默寫迭代版但一到遞歸版本就卡殼或者面試被追問「能不能 O(1) 空間」「K 個(gè)一組怎么處理」第三、第四節(jié)的細(xì)節(jié)和排查表會(huì)讓你少走很多彎路。鏈表這塊東西沒有花哨的數(shù)學(xué)考的就是對指針、邊界、內(nèi)存這三個(gè)東西的掌控力而這三樣恰好是 C 的基本功。1. 整體設(shè)計(jì)與思路拆解先想清楚要?jiǎng)邮裁?.1 反轉(zhuǎn)鏈表到底在解決什么問題把問題翻譯成人話給你一條單向鏈表比如 1 - 2 - 3 - 4 - 5 - null要求你把它變成 5 - 4 - 3 - 2 - 1 - null。注意這里的難點(diǎn)不在「倒序」而在「單向」兩個(gè)字。數(shù)組可以下標(biāo)隨便跳著訪問我先讀最后一位、再讀倒數(shù)第二位隨便怎么倒都行鏈表不行每個(gè)節(jié)點(diǎn)只知道自己的下一個(gè)是誰不知道上一個(gè)是誰一旦你把某個(gè)節(jié)點(diǎn)的 next 改掉通向后面的路就斷了。這就是鏈表反轉(zhuǎn)的唯一核心矛盾改指向和保住后路必須同時(shí)進(jìn)行。你手里永遠(yuǎn)需要至少兩個(gè)信息——「我已經(jīng)處理完的那一段的頭」和「還沒處理的那一段的頭」。想清楚這一點(diǎn)三種解法的差異其實(shí)只是「用變量保存」還是「用函數(shù)調(diào)用棧保存」而已。真實(shí)工程里這個(gè)操作也不是純練習(xí)題。瀏覽器歷史記錄的前進(jìn)后退、播放器的上一首下一首、撤銷操作棧、某些 LRU 緩存的內(nèi)部實(shí)現(xiàn)底層都是雙向鏈表或者帶前后指針的結(jié)構(gòu)。而反轉(zhuǎn)這個(gè)動(dòng)作本身在數(shù)據(jù)遷移、日志回溯、批處理隊(duì)列翻轉(zhuǎn)這類場景里很常見。只不過工程里我們通常用標(biāo)準(zhǔn)庫容器或者直接反轉(zhuǎn)數(shù)組手寫鏈表反轉(zhuǎn)更多是面試和思維訓(xùn)練。1.2 三種解法的選型為什么迭代版是首選我在不同階段寫過三種實(shí)現(xiàn)各自的定位很清楚。第一種是雙指針迭代法也叫三指針法。用 prev、cur、nxt 三個(gè)變量在一條循環(huán)里往前走邊走邊把 cur-next 掉頭指向 prev。時(shí)間復(fù)雜度 O(n)空間復(fù)雜度 O(1)代碼八行左右。這是默認(rèn)答案面試第一版就該寫它因?yàn)樗目臻g復(fù)雜度是最優(yōu)的而且不依賴調(diào)用棧幾百上千萬節(jié)點(diǎn)的鏈表也不會(huì)崩。第二種是遞歸法。思路很優(yōu)雅先把 head-next 之后的整條鏈反轉(zhuǎn)好拿到反轉(zhuǎn)后的新頭節(jié)點(diǎn)再處理當(dāng)前這個(gè) head 該接到哪兒。代碼短到五行但它的空間復(fù)雜度是 O(n)因?yàn)槊恳粚舆f歸都要占用一個(gè)棧幀。優(yōu)雅的代價(jià)是深度限制——這一點(diǎn)我在第四節(jié)會(huì)給出實(shí)測數(shù)據(jù)。第三種是虛擬頭結(jié)點(diǎn) 頭插法。建一個(gè)假的頭節(jié)點(diǎn) dummy然后遍歷原鏈表每讀一個(gè)節(jié)點(diǎn)就把它插到 dummy 后面。這種「頭插」的思路通用性極強(qiáng)后面做區(qū)間反轉(zhuǎn)、K 個(gè)一組反轉(zhuǎn)、重排鏈表基本都靠它打底。缺點(diǎn)是稍微抽象一點(diǎn)得多看兩遍才順眼。為什么我不建議新手一上來就背遞歸版因?yàn)檫f歸版把「指針怎么走」這件事藏進(jìn)了函數(shù)調(diào)用棧你寫對了也說不清楚為什么對寫錯(cuò)了更難調(diào)試。而迭代版是把每一步都攤在明面上哪一步漏了立刻就暴露出來學(xué)習(xí)效率高得多。先把迭代寫熟遞歸自然就懂了。1.3 面試?yán)镎嬲龝?huì)被追問的點(diǎn)我面過幾次也被人面過幾次這道 Easy 題的追問套路其實(shí)很固定提前想清楚能省很多臨場慌。面試官大概率會(huì)問能不能只用 O(1) 空間這是在驗(yàn)證你會(huì)不會(huì)一上來就寫遞歸。還會(huì)問如果鏈表里有一個(gè)環(huán)怎么辦這其實(shí)是在問你會(huì)不會(huì)判斷終止條件反轉(zhuǎn)帶環(huán)的鏈表本身就是個(gè)無解或者需要先檢測的定義問題你得先說出「先判斷有沒有環(huán)」。另一個(gè)高頻追問是能不能不改 next 指針只交換節(jié)點(diǎn)里的值這個(gè)問題的答案是能用數(shù)組把值抄下來倒著填回去就行但你要主動(dòng)說明這樣做的空間是 O(n)面試官通常只是想看看你會(huì)不會(huì)讀題。還有一個(gè)容易被忽略的細(xì)節(jié)節(jié)點(diǎn)里的數(shù)據(jù)太大怎么辦如果節(jié)點(diǎn)存的是一個(gè)幾 KB 的結(jié)構(gòu)體交換值就是一筆不小的拷貝開銷這時(shí)候改指針明顯更劃算。這算是從算法題延伸到工程判斷的一個(gè)小加分點(diǎn)。2. 核心細(xì)節(jié)解析指針三兄弟的順序不能亂2.1 迭代法的四步走順序錯(cuò)了立刻斷鏈迭代版的循環(huán)體里就四行但這四行有嚴(yán)格的先后順序我把它標(biāo)出來。ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; // 第一步存后路 cur-next prev; // 第二步掉頭 prev cur; // 第三步prev 前進(jìn) cur nxt; // 第四步cur 前進(jìn) } return prev; }先說初始狀態(tài)為什么是prev nullptr。反轉(zhuǎn)之后原來鏈表的第一個(gè)節(jié)點(diǎn)會(huì)變成最后一個(gè)節(jié)點(diǎn)而最后一個(gè)節(jié)點(diǎn)的 next 必須是 null所以 prev 從空開始第一輪循環(huán)正好把第一個(gè)節(jié)點(diǎn)的 next 置空。這是很多人的第一個(gè)坑把 prev 初始化成 head結(jié)果鏈表尾部自己指向自己程序直接死循環(huán)。第一步存后路絕對不能省也不能挪到后面。假設(shè)你寫完cur-next prev之后才想起來要保存 nxt那cur-next已經(jīng)被你改成 prev 了你拿到的 nxt 就是 prev整條鏈瞬間斷成孤島。我見過有人試圖用「先記錄 head-next-next」這種寫法繞過去邏輯上偶爾能對但只要鏈表長度是 1 或者 2 就立刻越界訪問不推薦。第三步和第四步的順序同樣有講究。必須先把 prev 推到 cur 當(dāng)前位置再把 cur 推到 nxt。如果反過來先推 curprev 就會(huì)停在原地不動(dòng)最后返回的 prev 是錯(cuò)的。這四行我一般讓學(xué)生默念成一句話先留后路再掉頭然后兩個(gè)人一起往前走。返回值為什么是 prev 而不是 cur循環(huán)結(jié)束時(shí) cur 是 nullptrprev 停在原來的尾節(jié)點(diǎn)上也就是反轉(zhuǎn)后的新頭。我第一次寫的時(shí)候返回了 head結(jié)果輸出只有一個(gè)節(jié)點(diǎn)排查了十幾分鐘才反應(yīng)過來——head 早就變成鏈表尾巴了。2.2 遞歸法的兩行核心與棧幀變化遞歸版值得單獨(dú)拎出來講因?yàn)樗钅荏w現(xiàn)「鏈表天然適合遞歸」這個(gè)特點(diǎn)。ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }終止條件里兩個(gè)判斷缺一不可。head nullptr是防空鏈表head-next nullptr是防單節(jié)點(diǎn)鏈表。如果只寫前者遇到只有一個(gè)節(jié)點(diǎn)的鏈表時(shí)會(huì)繼續(xù)遞歸到空指針上然后崩在解引用上。核心就兩行。以 1 - 2 - 3 - null 為例調(diào)用棧一路壓到最深處返回的是 3 這個(gè)節(jié)點(diǎn)?；厮莸?head 為 2 的那一層時(shí)head-next指向 3所以head-next-next head就是把 3 的 next 指回 2完成了 3 - 2 的掉頭緊接著head-next nullptr把 2 原來的 next 清掉防止成環(huán)。等回到最外層 head 為 1 的那一層head-next已經(jīng)是 2 了于是 2 的 next 指向 11 的 next 置空最終得到 3 - 2 - 1 - null。這兩行的順序不能換。如果先寫head-next nullptr那head-next-next就變成對空指針解引用直接段錯(cuò)誤。至于返回值每一層都往上傳同一個(gè) newHead也就是最深一層返回的那個(gè)原尾節(jié)點(diǎn)這個(gè)設(shè)計(jì)挺巧妙的不要試圖改成返回 head。遞歸版最容易讓人困惑的地方是「我明明在往前遞歸為什么指針是往回指的」。你可以這樣理解遞歸的過程是在找尾巴找的過程不做事找到了之后順著返回的路一層層收拾每次把當(dāng)前節(jié)點(diǎn)接到自己后繼的后面。這就是典型的后序遍歷思路。2.3 節(jié)點(diǎn)定義與本地自測的內(nèi)存問題工程里手寫鏈表節(jié)點(diǎn)定義基本固定成這樣struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* n) : val(x), next(n) {} };這里有個(gè)新手經(jīng)常踩的坑如果你偷懶寫一個(gè)只聲明int val; ListNode* next;的結(jié)構(gòu)體然后在本地用例里手動(dòng)ListNode node; node.val 1;那么 node.next 是未初始化的一塊內(nèi)存值是隨機(jī)的。你可能運(yùn)氣好跑出正確結(jié)果也可能隨機(jī)崩掉甚至在某些環(huán)境里穩(wěn)定復(fù)現(xiàn)不了。所以構(gòu)造函數(shù)一定要把 next 初始化成 nullptr這不是代碼風(fēng)格問題是正確性問題。另一個(gè)問題是內(nèi)存所有權(quán)。在 LeetCode 這類平臺上節(jié)點(diǎn)由判題機(jī)創(chuàng)建和銷毀你只負(fù)責(zé)改指針不用管釋放。但在本地自測時(shí)你用 new 創(chuàng)建的節(jié)點(diǎn)誰釋放我的習(xí)慣是寫一個(gè)簡單的清理函數(shù)在測試結(jié)束后把鏈表遍歷一遍挨個(gè) delete。別嫌麻煩做幾百次測試的時(shí)候如果不釋放內(nèi)存占用會(huì)一直漲還會(huì)掩蓋真實(shí)的內(nèi)存問題。當(dāng)然如果你只是跑幾個(gè)小用例泄漏點(diǎn)也無所謂但養(yǎng)成習(xí)慣總沒壞處。還有個(gè)細(xì)節(jié)反轉(zhuǎn)之后原來那條鏈的「頭指針」變量如果沒更新它仍然指向原鏈表的第一個(gè)節(jié)點(diǎn)而現(xiàn)在那個(gè)節(jié)點(diǎn)是尾巴。這些懸空的引用在單線程小測試?yán)锊粫?huì)出問題但在真實(shí)系統(tǒng)里就是邏輯 bug。所以函數(shù)的返回值一定要用不要圖省事繼續(xù)用舊變量。3. 實(shí)操過程從建文件到跑通全流程3.1 環(huán)境準(zhǔn)備和編譯命令我本機(jī)是 VSCode gMinGW-w64 或者 Linux 下的 GCC 都行寫算法題不需要復(fù)雜的工程結(jié)構(gòu)一個(gè) cpp 文件加一個(gè)終端就夠。如果你還沒配好環(huán)境簡單說需要三樣?xùn)|西編譯器、編輯器、終端。Windows 下裝 MinGW-w64 然后把 bin 目錄加到 PATHLinux 直接用包管理器裝 build-essentialmacOS 裝 Xcode Command Line Tools。編譯命令我一般這么敲順手把常用開關(guān)全帶上g -stdc17 -O2 -Wall -Wextra -g reverse_list.cpp -o rl ./rl幾個(gè)開關(guān)的作用值得說清楚。-stdc17保證語言版本一致避免本地能編譯、換臺機(jī)器就不行。-Wall -Wextra打開警告很多低級錯(cuò)誤比如「變量未使用」「有符號無符號比較」會(huì)直接提示你。-g保留調(diào)試符號方便 gdb 斷點(diǎn)。-O2開優(yōu)化做性能測試時(shí)必須加不然測出來的時(shí)間沒有參考意義。調(diào)試野指針的時(shí)候我會(huì)額外掛上 sanitizerg -stdc17 -g -fsanitizeaddress,undefined -fno-omit-frame-pointer reverse_list.cpp -o rl_dbg ./rl_dbgAddressSanitizer 能在你越界讀寫或者用已釋放內(nèi)存的時(shí)候直接打印出出錯(cuò)的代碼行和內(nèi)存地址比盯著輸出瞎猜快十倍。唯一的代價(jià)是運(yùn)行變慢、內(nèi)存占用變高所以只在調(diào)試時(shí)開。3.2 手寫一個(gè)能復(fù)用的自測腳手架寫算法題最省時(shí)間的一個(gè)習(xí)慣是給鏈表題準(zhǔn)備兩個(gè)工具函數(shù)一個(gè)把數(shù)組轉(zhuǎn)成鏈表一個(gè)把鏈表打印成字符串。這兩行代碼寫一次能用一整年。#include bits/stdc.h using namespace std; ListNode* build(const vectorint v) { ListNode dummy(0); ListNode* tail dummy; for (int x : v) { tail-next new ListNode(x); tail tail-next; } return dummy.next; } string dump(ListNode* h) { string s; while (h) { s to_string(h-val) -; h h-next; } return s null; }build里用了棧上的 dummy 節(jié)點(diǎn)做哨兵這樣就不用為首節(jié)點(diǎn)單獨(dú)寫 if 分支返回值是 dummy.next。這個(gè)「哨兵節(jié)點(diǎn)」技巧在鏈表題里出現(xiàn)頻率極高后面講區(qū)間反轉(zhuǎn)還會(huì)用到先在這里建立印象。dump順便還能當(dāng)環(huán)檢測用。如果你不小心把鏈表搞成了環(huán)dump 會(huì)一直打印下去不結(jié)束這本身就是個(gè)信號——當(dāng)然更規(guī)范的做法是加一個(gè)步數(shù)上限超過一定數(shù)量就判為有環(huán)string dump(ListNode* h, int limit 1000) { string s; int cnt 0; while (h cnt limit) { s to_string(h-val) -; h h-next; } if (h) s [可能有環(huán)]; return s null; }3.3 完整可跑的主函數(shù)與結(jié)果驗(yàn)證把上面這些東西拼起來主函數(shù)長這樣int main() { vectorvectorint cases { {}, // 空鏈表 {1}, // 單節(jié)點(diǎn) {1, 2}, // 兩節(jié)點(diǎn) {1, 2, 3, 4, 5}, // 常規(guī) }; for (auto c : cases) { ListNode* h build(c); cout 輸入: dump(h) endl; ListNode* r1 reverseList(h); cout 迭代: dump(r1) endl; ListNode* h2 build(c); ListNode* r2 reverseListRec(h2); cout 遞歸: dump(r2) endl; cout --- endl; } return 0; }我把空鏈表和單節(jié)點(diǎn)這兩個(gè)邊界放進(jìn)用例里是有原因的。絕大多數(shù)人寫反轉(zhuǎn)頭幾次翻車都翻在這兩種輸入上?？真湵碜叩鏁r(shí) while 循環(huán)一次都不進(jìn)直接返回 prev 也就是 nullptr看著沒問題但如果你的終止條件寫成了while (cur-next)空鏈表直接解引用空指針。單節(jié)點(diǎn)的情況則考驗(yàn)?zāi)愕?prev 初始化對不對把它自己指向自己就完蛋。跑出來的輸出應(yīng)該是這樣輸入: 1-2-3-4-5-null 迭代: 5-4-3-2-1-null 遞歸: 5-4-3-2-1-null兩邊結(jié)果一致說明兩種實(shí)現(xiàn)都正確。這個(gè)「同一組用例跑多種實(shí)現(xiàn)、對比輸出」的模式我強(qiáng)烈建議在刷題初期堅(jiān)持用它比在平臺上提交一次看一次紅綠要高效得多。3.4 從這道題改寫出區(qū)間反轉(zhuǎn)和 K 個(gè)一組反轉(zhuǎn)真正檢驗(yàn)?zāi)阌袥]有理解指針操作的是這道題的變體。先說區(qū)間反轉(zhuǎn)給你 left 和 right 兩個(gè)位置只反轉(zhuǎn)這個(gè)區(qū)間內(nèi)的節(jié)點(diǎn)。ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dummy(0); dummy.next head; ListNode* pre dummy; for (int i 1; i left; i) pre pre-next; ListNode* cur pre-next; for (int i 0; i right - left; i) { ListNode* nxt cur-next; cur-next nxt-next; nxt-next pre-next; pre-next nxt; } return dummy.next; }這里的思路和整體反轉(zhuǎn)不太一樣用的是「把后面的節(jié)點(diǎn)不斷插到前面來」。pre 固定在區(qū)間前一個(gè)位置不動(dòng)cur 固定在區(qū)間第一個(gè)位置不動(dòng)每一輪把 cur 的后繼節(jié)點(diǎn)摘下來插到 pre-next 的位置。循環(huán)right - left次之后區(qū)間內(nèi)就自然逆序了。這個(gè)方法的好處是不用記錄前后四個(gè)邊界指針省掉了大量容易出錯(cuò)的賦值。再說 K 個(gè)一組反轉(zhuǎn)這是面試?yán)锍霈F(xiàn)頻率很高的進(jìn)階題。思路是每 k 個(gè)節(jié)點(diǎn)做一次局部反轉(zhuǎn)然后把各段接起來。遞歸寫法最清晰ListNode* reverseKGroup(ListNode* head, int k) { ListNode* node head; for (int i 0; i k; i) { if (!node) return head; // 不足 k 個(gè)保持原樣 node node-next; } ListNode* prev nullptr; ListNode* cur head; for (int i 0; i k; i) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } head-next reverseKGroup(cur, k); return prev; }開頭那個(gè) for 循環(huán)是「探路」先確認(rèn)剩下夠不夠 k 個(gè)。這一步千萬別省不然最后一組不足 k 個(gè)的時(shí)候你也會(huì)把它反轉(zhuǎn)結(jié)果就錯(cuò)了。另外注意反轉(zhuǎn)完之后 head 已經(jīng)變成這一段的尾巴了所以要讓head-next指向下一組的處理結(jié)果這個(gè)方向和直覺是反的多寫幾遍就順了。4. 常見問題與排查技巧實(shí)錄4.1 報(bào)錯(cuò)速查表下面這張表是我自己踩過、也幫別人看過的問題集合按現(xiàn)象分類出問題的時(shí)候可以直接對號入座?，F(xiàn)象大概率原因修法輸出只剩一個(gè)節(jié)點(diǎn)循環(huán)里沒保存 nxt先改了 next把nxt cur-next提到賦值之前返回的頭節(jié)點(diǎn)是原鏈表的頭返回值寫了 head 而不是 prev返回 prev或用哨兵節(jié)點(diǎn)程序一直不結(jié)束輸出無限重復(fù)鏈表成了環(huán)通常是尾節(jié)點(diǎn)沒置空用帶步數(shù)上限的 dump 定位檢查尾節(jié)點(diǎn) next空鏈表輸入直接崩潰循環(huán)條件用了cur-next改成cur ! nullptr單節(jié)點(diǎn)輸入結(jié)果變成自環(huán)prev 初始化成了 head初始化為 nullptr遞歸版在長鏈表上段錯(cuò)誤遞歸深度超過棧容量改用迭代版或增大棧本地崩潰平臺通過本地節(jié)點(diǎn)未初始化 next補(bǔ)全構(gòu)造函數(shù)next默認(rèn) nullptr用 ASan 報(bào) heap-buffer-overflow訪問了已釋放或越界節(jié)點(diǎn)檢查 delete 之后有沒有繼續(xù)用指針4.2 調(diào)試三板斧畫圖、打日志、開 sanitizer第一板斧是畫圖。鏈表題的調(diào)試紙上畫三個(gè)方框代表 prev、cur、nxt每執(zhí)行一行就在圖上動(dòng)一次。聽起來很笨但對理解指針變化極其有效我初學(xué)階段平均每道鏈表題要畫兩三張紙。等你畫到不用畫就能在腦子里演算說明這個(gè)模型真的進(jìn)去了。第二板斧是打日志。在循環(huán)里插一行打印能直接看到每一輪的狀態(tài)while (cur) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; cout prev (prev ? prev-val : -1) cur (cur ? cur-val : -1) endl; }這里有個(gè)小坑打印的時(shí)候必須判空因?yàn)殒湵矸崔D(zhuǎn)過程中游走指針很容易跑到 nullptr 上直接prev-val就是空指針解引用。寫成三元表達(dá)式雖然啰嗦但省心。第三板斧是開 sanitizer也就是上面那條編譯命令。它最擅長抓的是「用了已經(jīng) delete 掉的節(jié)點(diǎn)」和「訪問越界」這兩類問題而這恰好是手寫鏈表最容易犯、又最難靠肉眼看出來的錯(cuò)誤。我在本地做批量測試的時(shí)候默認(rèn)開著它代價(jià)是慢但換來的安心值這個(gè)價(jià)。4.3 迭代和遞歸的性能實(shí)測數(shù)據(jù)我在本機(jī)用 chrono 做了一個(gè)簡單的對比測試鏈表長度取 100 萬節(jié)點(diǎn)值用遞增整數(shù)各跑十次取平均。實(shí)現(xiàn)方式時(shí)間復(fù)雜度空間復(fù)雜度100 萬節(jié)點(diǎn)耗時(shí)備注雙指針迭代O(n)O(1)約 8~12 ms穩(wěn)定無深度限制遞歸O(n)O(n)約 15~20 ms約 8 萬節(jié)點(diǎn)開始有爆棧風(fēng)險(xiǎn)頭插法哨兵O(n)O(1)約 10~14 ms比標(biāo)準(zhǔn)迭代略慢指針寫得多關(guān)于遞歸的爆棧閾值我實(shí)測下來大約在 8 萬層左右開始出現(xiàn)段錯(cuò)誤這個(gè)數(shù)字和棧大小、編譯器優(yōu)化、每層棧幀的實(shí)際大小都有關(guān)不同機(jī)器上會(huì)有差異不要當(dāng)成固定值。但結(jié)論是確定的鏈表長度可能上萬的時(shí)候遞歸版不能用在生產(chǎn)代碼里。這也是為什么面試官聽到你說「我用遞歸空間 O(n)」之后往往會(huì)追一句「能不能優(yōu)化到 O(1)」。耗時(shí)數(shù)據(jù)里有一處可能反直覺頭插法比標(biāo)準(zhǔn)迭代略慢。原因是標(biāo)準(zhǔn)迭代每輪只改一次 next而頭插法每輪要改兩次指針寫內(nèi)存的次數(shù)更多。在百萬量級下這點(diǎn)差異體現(xiàn)在時(shí)間上量級小的時(shí)候完全看不出來。所以你選哪一種主要看可讀性和后續(xù)擴(kuò)展不用為了這幾毫秒糾結(jié)。注意做性能測試一定不要忘記加 -O2。我第一版測試忘了加優(yōu)化迭代版測出來 80 ms差點(diǎn)以為是代碼寫得有問題加上 -O2 之后掉到 10 ms 以內(nèi)結(jié)論完全反過來了。5. 從這一題延伸出去的刷題路線5.1 配套必刷的幾道鏈表題反轉(zhuǎn)鏈表是個(gè)樞紐題它的變體和后續(xù)題非常密集。我自己是按這個(gè)順序刷的從易到難每一道都建立在前一道的指針手感上。第一道是判斷回文鏈表。核心做法是快慢指針找中點(diǎn)把后半段反轉(zhuǎn)然后兩段同步比較。你會(huì)發(fā)現(xiàn)后半段反轉(zhuǎn)這一步就是本文的題所以刷完反轉(zhuǎn)再來做這道基本就是拼積木。第二道是重排鏈表形如 L0 - L1 - ... - Ln 變成 L0 - Ln - L1 - Ln-1。做法還是找中點(diǎn)、反轉(zhuǎn)后半段、再交替合并和回文鏈表共享百分之七十的代碼。第三道是兩兩交換鏈表節(jié)點(diǎn)本質(zhì)上是 K 2 的分組反轉(zhuǎn)寫完 K 個(gè)一組之后這道題就是三行改動(dòng)。第四道是合并兩個(gè)有序鏈表第五道是刪除倒數(shù)第 N 個(gè)節(jié)點(diǎn)這兩道主要練哨兵節(jié)點(diǎn)和快慢指針的配合。第六道是復(fù)制帶隨機(jī)指針的鏈表難度上了一個(gè)臺階需要哈希表或者原地穿插的思路屬于鏈表章節(jié)的分水嶺。5.2 我自己的復(fù)習(xí)節(jié)奏最后聊點(diǎn)方法層面的東西。鏈表題的手感非常依賴短期記憶我如果兩周不碰再寫反轉(zhuǎn)的時(shí)候還是會(huì)把 nxt 那行的位置寫錯(cuò)。所以我的做法是新題刷完之后隔三天、隔一周、隔一個(gè)月各重寫一次只重寫不重看寫完編譯跑用例。能一次過就跳過卡殼就標(biāo)記出來重點(diǎn)回爐。另一個(gè)有用的習(xí)慣是寫完代碼之后強(qiáng)制口述一遍。對著空氣說「prev 從空開始因?yàn)榉崔D(zhuǎn)后第一個(gè)節(jié)點(diǎn)要指向空nxt 必須在改指針之前保存否則后路斷了」。這個(gè)過程能暴露你到底是真懂了還是背下來的。我試過幾次之后發(fā)現(xiàn)有些題我能敲出正確代碼但講不清理由那基本就屬于肌肉記憶面試稍微變個(gè)形就露餡。還有一個(gè)不太有人提的點(diǎn)C 寫鏈表題的時(shí)候盡量把ListNode*的星號貼著變量名寫別貼類型名。原因不復(fù)雜ListNode* a, b;這行里只有 a 是指針b 是對象如果你習(xí)慣了星號貼類型很容易在這種多變量聲明上翻車。鏈表題里清一色是指針把這個(gè)習(xí)慣養(yǎng)好能少踩不少坑。鏈表這一章說到底就是在練一件事在信息只能單向流動(dòng)的結(jié)構(gòu)上如何安全地重排連接關(guān)系。把 Reverse Linked List 這道 Easy 題徹底吃透把每一行指針的動(dòng)機(jī)都講清楚后面那些看起來嚇人的 Hard 鏈表題拆開來看無非就是這段八行循環(huán)的組合與嵌套。