上個(gè)周末我?guī)鸵粋€(gè)朋友做模擬面試隨手挑了LeetCode 19這道刪除鏈表倒數(shù)第 N 個(gè)結(jié)點(diǎn)的題。他面過(guò)這道題上來(lái)就寫了快慢指針代碼格式和命名都很規(guī)范可我問(wèn)了一句“為什么 fast 要先走 n1 步slow 要從 dummy 出發(fā)而不是從 head 出發(fā)”他愣了半天最后承認(rèn)自己是背的模板。這道題在 LeetCode 上常見的主流思路一共有三類長(zhǎng)度法、快慢指針、棧表面是三種寫法內(nèi)里全是鏈表題最經(jīng)典的差一問(wèn)題。如果你正準(zhǔn)備面試或者剛開始刷鏈表題這篇內(nèi)容想把三種解法的原理、代碼、邊界和踩坑經(jīng)驗(yàn)一次講清楚。我當(dāng)時(shí)追問(wèn)他三個(gè)問(wèn)題鏈表長(zhǎng)度怎么求倒數(shù)第 N 個(gè)結(jié)點(diǎn)的“前驅(qū)”是誰(shuí)如果刪的是頭結(jié)點(diǎn)怎么辦這三個(gè)問(wèn)題答明白這道題才算真正會(huì)了。下面不繞彎子直接從頭開始拆。1. 先看題倒數(shù)第 N 個(gè)天然就是單向鏈表的陷阱1.1 題面回顧與“倒數(shù)”的本質(zhì)題目描述非常簡(jiǎn)單給定一個(gè)單鏈表 head刪除倒數(shù)第 n 個(gè)結(jié)點(diǎn)返回頭結(jié)點(diǎn)。n 是有效值也就是 1 ≤ n ≤ 鏈表長(zhǎng)度。這個(gè)“有效”條件很重要它省去了很多邊界校驗(yàn)的啰嗦但并沒有省去我們對(duì)邊界條件的思考。單鏈表的結(jié)構(gòu)決定了它只能從 head 一路 next 往后走不能回頭看。數(shù)組里你要?jiǎng)h倒數(shù)第 n 個(gè)元素直接算下標(biāo) arr.length - n 就行鏈表不行因?yàn)殒湵淼摹跋聵?biāo)”和內(nèi)存位置沒有隨機(jī)訪問(wèn)能力。倒數(shù)第 n 個(gè)翻譯成正數(shù)就是第 L - n 1 個(gè)L 為鏈表長(zhǎng)度。要?jiǎng)h的是這個(gè)節(jié)點(diǎn)本身可單鏈表刪除的實(shí)質(zhì)是修改前驅(qū)節(jié)點(diǎn)的 next所以你真正要找的是第 L - n 個(gè)節(jié)點(diǎn)也就是待刪節(jié)點(diǎn)的前驅(qū)。這個(gè)“正數(shù)是第幾個(gè)”和“要操作哪個(gè)指針”之間就是差一問(wèn)題開始的地方。很多人寫錯(cuò)不是代碼能力不行而是沒有意識(shí)到刪除操作和查找操作的目標(biāo)不一樣。1.2 dummy 節(jié)點(diǎn)不是技巧是刪除頭結(jié)點(diǎn)時(shí)唯一體面的方式當(dāng)待刪節(jié)點(diǎn)恰好是頭結(jié)點(diǎn)時(shí)它沒有前驅(qū)。這時(shí)候常規(guī)的prev-next target-next根本寫不出來(lái)因?yàn)?prev 不存在。新手最常見的處理是單獨(dú)寫一個(gè) if 判斷是不是頭結(jié)點(diǎn)再分兩條路走。我不是說(shuō)這樣不行而是這樣的代碼分支多邊界容易漏。更干凈的做法是新建一個(gè)啞節(jié)點(diǎn) dummy讓 dummy-next 指向 head。不管要?jiǎng)h的是頭結(jié)點(diǎn)還是中間節(jié)點(diǎn)在邏輯上 dummy 都充當(dāng) head 的前驅(qū)。最后返回 dummy-next 即可。用這個(gè)技巧三種解法都能把“刪除頭結(jié)點(diǎn)”和“刪除普通節(jié)點(diǎn)”統(tǒng)一成同一段邏輯。我之前幫人 code review 時(shí)見過(guò)一個(gè)反面案例他用了 dummy 之后還在代碼里單獨(dú)判斷if (n length) head head-next;看起來(lái)小心翼翼實(shí)際完全多余。記住這一條——只要加了 dummy就不要單獨(dú)處理頭結(jié)點(diǎn)。2. 解法一長(zhǎng)度法——先數(shù)清楚再動(dòng)手2.1 思路與代碼兩次遍歷把倒數(shù)換算成正數(shù)長(zhǎng)度法的思路最直白先完整遍歷一次鏈表數(shù)出總長(zhǎng)度 L。然后倒數(shù)第 n 個(gè)就是正數(shù)第 L - n 1 個(gè)刪除它需要拿到第 L - n 個(gè)節(jié)點(diǎn)作前驅(qū)于是從 dummy 出發(fā)走 L - n 步就能停在待刪節(jié)點(diǎn)的前驅(qū)上。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); int length 0; ListNode* cur head; while (cur) { length; cur cur-next; } // 從 dummy 出發(fā)走 length - n 步停在待刪節(jié)點(diǎn)的前驅(qū) ListNode* prev dummy; for (int i 0; i length - n; i) { prev prev-next; } ListNode* target prev-next; prev-next target-next; delete target; ListNode* newHead dummy-next; delete dummy; return newHead; }舉個(gè)例子鏈表是 1 - 2 - 3 - 4 - 5n 2。L 5length - n 3。dummy 是第 0 個(gè)位置走 3 步到節(jié)點(diǎn) 3節(jié)點(diǎn) 3 正是倒數(shù)第 2 個(gè)節(jié)點(diǎn)也就是節(jié)點(diǎn) 4 的前驅(qū)。然后prev-next target-next就把 3 的 next 從 4 改到 5 了。這里的推導(dǎo)值得稍微展開一下。倒數(shù)第 n 個(gè)節(jié)點(diǎn)是正數(shù)第 L - n 1 個(gè)它的前驅(qū)是正數(shù)第 L - n 個(gè)。dummy 位于所有節(jié)點(diǎn)之前算第 0 個(gè)所以從 dummy 出發(fā)走 L - n 步恰好到達(dá)第 L - n 個(gè)節(jié)點(diǎn)。每一步都是樸素的 next 移動(dòng)不需要再做加法減法。2.2 長(zhǎng)度法的三個(gè)容易寫錯(cuò)的地方第一統(tǒng)計(jì)長(zhǎng)度時(shí)用while (cur)而不是while (cur-next)。前者走到 nullptr 才停length 正好是節(jié)點(diǎn)個(gè)數(shù)后者雖然也能數(shù)出長(zhǎng)度但在空鏈表上會(huì)直接解引用空指針。LeetCode 的測(cè)試用例很少給空鏈表但本地測(cè)試時(shí)你一定會(huì)踩到。第二第二個(gè)循環(huán)的邊界是i length - n不是i length - n。多加一個(gè)等號(hào)prev 就從“前驅(qū)”變成“待刪節(jié)點(diǎn)”后面刪除時(shí)你還得再記一個(gè)更前面的節(jié)點(diǎn)代碼瞬間就從兩行變成五行。第三最終必須返回dummy-next不能圖省事返回 head。當(dāng) n 等于鏈表長(zhǎng)度時(shí)head 就是被刪除的那個(gè)節(jié)點(diǎn)代碼里已經(jīng)delete target了再返回 head 就是返回一個(gè)懸空指針本地跑起來(lái)程序直接崩。2.3 什么時(shí)候長(zhǎng)度法并不差很多文章把長(zhǎng)度法叫“笨辦法”我不太同意。在 LeetCode 這種判斷題里它確實(shí)多遍歷了一次可實(shí)際工程里鏈表經(jīng)常會(huì)自帶長(zhǎng)度字段比如標(biāo)準(zhǔn)庫(kù)的 LinkedList 都有 size() 接口。如果鏈表類本身維護(hù)了 size長(zhǎng)度法實(shí)際上就是一次遍歷時(shí)間復(fù)雜度低邏輯也最好懂。即便沒有 size 字段長(zhǎng)度法在面試中也很有價(jià)值它是你能最快寫出、最不容易出錯(cuò)的思路。面試時(shí)你可以先給長(zhǎng)度法證明你會(huì)分析問(wèn)題然后主動(dòng)說(shuō)“如果面試官要求一次遍歷我還有優(yōu)化方案”這比一上來(lái)就甩一個(gè)快慢指針模板要自然得多。3. 解法二快慢指針——一次遍歷的真相與邊界細(xì)節(jié)3.1 關(guān)鍵設(shè)計(jì)為什么 fast 要先走 n1 步快慢指針的代碼識(shí)別度很高但真正理解它的人并不多。設(shè)計(jì)是這樣的fast、slow 都從 dummy 出發(fā)fast 先走 n1 步然后 fast 和 slow 一起每次走一步。當(dāng) fast 到達(dá) nullptr 時(shí)slow 停的位置恰好是待刪節(jié)點(diǎn)的前驅(qū)。核心問(wèn)題來(lái)了為什么是 n1不是 n假設(shè) fast 只先走 n 步兩指針之間拉開的距離是 n 個(gè)節(jié)點(diǎn)。fast 到末尾時(shí)slow 與末尾之間也隔著 n 個(gè)節(jié)點(diǎn)所以 slow 正好指向待刪節(jié)點(diǎn)本身?？蓜h除需要的是前驅(qū)你后面還得補(bǔ)一個(gè)變量記住 slow 前面的節(jié)點(diǎn)或者用ListNode* tmp slow-next; slow-next slow-next-next之類的寫法雖然也能刪但通用性差一些。讓 fast 先走 n1 步slow 和 fast 之間保持 n1 個(gè)節(jié)點(diǎn)的距離。fast 到 nullptr 時(shí)slow 和末尾之間隔著 n1 個(gè)節(jié)點(diǎn)位置也就是說(shuō) slow 是倒數(shù)第 n1 個(gè)節(jié)點(diǎn)剛好是倒數(shù)第 n 個(gè)節(jié)點(diǎn)的前驅(qū)。之所以能從 dummy 出發(fā)是因?yàn)?dummy 在 head 前面補(bǔ)了一個(gè)位置讓“刪除頭結(jié)點(diǎn)”也變成普通情況。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* fast dummy; ListNode* slow dummy; // fast 先走 n1 步 for (int i 0; i n; i) { fast fast-next; } // 然后同步走 while (fast ! nullptr) { fast fast-next; slow slow-next; } ListNode* target slow-next; slow-next target-next; delete target; ListNode* newHead dummy-next; delete dummy; return newHead; }3.2 指針移動(dòng)軌跡推演光講概念不夠我建議你自己在紙上走一遍。拿 1 - 2 - 3 - 4 - 5n 2 為例。fast 先走 3 步從 dummy 走到節(jié)點(diǎn) 3slow 還在 dummy。接下來(lái)進(jìn)入 while 循環(huán)第 1 輪fast 從 3 走到 4slow 從 dummy 走到 1第 2 輪fast 從 4 走到 5slow 從 1 走到 2第 3 輪fast 從 5 走到 nullptrslow 從 2 走到 3此時(shí) fast 是 nullptr循環(huán)結(jié)束slow 正好在節(jié)點(diǎn) 3slow-next就是待刪的節(jié)點(diǎn) 4。這個(gè)走位非常規(guī)整但如果你把 fast 先走 n 步同樣的鏈表最終 slow 會(huì)停在節(jié)點(diǎn) 4 本身多出來(lái)的那一步就是天壤之別。還有一種常見寫法是 fast 先走 n 步然后讓 slow 從 dummy 出發(fā)fast 走到最后一個(gè)節(jié)點(diǎn)fast-next nullptr時(shí)停止slow 恰好也是停在待刪節(jié)點(diǎn)的前驅(qū)。這種寫法也能跑通但我個(gè)人不推薦混搭因?yàn)椤癴ast 先走 n1 步 循環(huán)條件 while(fast)”是一套自洽的組合改變?nèi)魏我粋€(gè)位置都會(huì)偏差。3.3 面試追問(wèn)“你能一次遍歷嗎”背后的考察點(diǎn)面試官讓你優(yōu)化成一次遍歷考察的不是記憶力而是你有沒有真正理解“用距離差模擬倒數(shù)”的思想。所以回答快慢指針時(shí)主動(dòng)說(shuō)出這幾件事fast 和 slow 為什么要保持 n1 的距離、dummy 的作用是什么、循環(huán)終止條件為什么用while (fast ! nullptr)。如果面試官進(jìn)一步問(wèn)“鏈表能不能真的從后往前走”你可以順勢(shì)說(shuō)單鏈表沒有反向引用所以只能用這種“先發(fā)射一個(gè)探針再讓慢指針跟隨”的思路。這本質(zhì)上是一種延遲執(zhí)行現(xiàn)實(shí)里也有對(duì)應(yīng)場(chǎng)景比如接收數(shù)據(jù)流時(shí)要等緩沖區(qū)積攢到一定長(zhǎng)度再處理模式類似?？臻g上快慢指針只用了兩個(gè)額外指針是 O(1)時(shí)間復(fù)雜度 O(L)每個(gè)節(jié)點(diǎn)最多被 fast 訪問(wèn)一次slow 再訪問(wèn)一次嚴(yán)格說(shuō)常數(shù)是 2但大 O 就是 O(L)。4. 解法三?！每臻g換一種直白的思考方式4.1 把“倒數(shù)”翻譯成“先進(jìn)后出”快慢指針用物理距離模擬倒數(shù)棧則用先進(jìn)后出的特性天然處理倒數(shù)。你只需要做兩件事先把鏈表從頭到尾壓入棧然后從棧頂彈出 n 個(gè)節(jié)點(diǎn)。第 n 次彈出的節(jié)點(diǎn)就是待刪節(jié)點(diǎn)彈出后新的棧頂恰好是它的前驅(qū)。這個(gè)解法我第一次見時(shí)覺得有點(diǎn)“繞”但后來(lái)想通了棧把“遍歷方向”完全反轉(zhuǎn)了鏈表從頭到尾入棧棧頂就是鏈表尾。倒數(shù)第 n 個(gè)節(jié)點(diǎn)相當(dāng)于正數(shù)第 n 次從棧頂彈出。算法題里當(dāng)你要從尾到頭處理數(shù)據(jù)時(shí)棧往往是最直接的數(shù)據(jù)結(jié)構(gòu)。這里的 dummy 依然有必要。如果棧里沒有 dummy刪除頭結(jié)點(diǎn)時(shí)彈出 n 次后?？赡芤呀?jīng)空了取前驅(qū)就成了空棧操作。讓 dummy 最先入棧墊底既保證了刪除頭結(jié)點(diǎn)時(shí)前驅(qū)存在又統(tǒng)一了代碼邏輯。4.2 C 實(shí)現(xiàn)與內(nèi)存語(yǔ)義ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); stackListNode* st; ListNode* cur dummy; while (cur) { st.push(cur); cur cur-next; } ListNode* target nullptr; for (int i 0; i n; i) { target st.top(); st.pop(); } ListNode* prev st.top(); // 棧里一定有 dummy所以不會(huì)空 prev-next target-next; delete target; ListNode* newHead dummy-next; delete dummy; return newHead; }注意棧里存的是ListNode*指針不是 int 值。如果你寫成stackListNode每次 push 都會(huì)復(fù)制一整個(gè)節(jié)點(diǎn)浪費(fèi)空間還改變了指針關(guān)系。這種對(duì)象拷貝的錯(cuò)誤很隱蔽編譯器不會(huì)報(bào)錯(cuò)但內(nèi)存占用和邏輯都會(huì)出問(wèn)題?？臻g復(fù)雜度是 O(L)因?yàn)樵跇O端情況下整個(gè)鏈表都會(huì)進(jìn)棧。在 n 很小的時(shí)候確實(shí)浪費(fèi)但它的優(yōu)勢(shì)是語(yǔ)義直白、幾乎不需要理解快慢指針的那種“距離差”技巧。面試場(chǎng)景下如果你前面已經(jīng)講了長(zhǎng)度法和快慢指針再補(bǔ)一句“用棧也能做”會(huì)顯得你掌握的不是一個(gè)孤立模板而是一整套解決問(wèn)題的工具箱。4.3 棧解法的工程啟發(fā)棧解法看起來(lái)只是“多了一種思路”但它在實(shí)際工程里的對(duì)應(yīng)場(chǎng)景很常見。舉個(gè)例子編輯器的撤銷功能你要撤銷最近一次操作本質(zhì)就是把操作記錄壓棧然后從棧頂彈出回滾編譯器檢查括號(hào)匹配也是把左括號(hào)壓棧遇到右括號(hào)彈棧。這道題用棧做確實(shí)不是最優(yōu)空間解但它揭示了“數(shù)據(jù)結(jié)構(gòu)的先進(jìn)后出特性可以扭轉(zhuǎn)遍歷順序”這一思想。當(dāng)你以后遇到需要倒序處理線性數(shù)據(jù)的業(yè)務(wù)比如日志倒查、導(dǎo)航回退可以第一時(shí)間想到棧這就是刷這道題收獲的一部分。5. 三種解法橫評(píng)筆試、面試、工程怎么選5.1 復(fù)雜度對(duì)照表解法時(shí)間復(fù)雜度空間復(fù)雜度遍歷次數(shù)代碼量典型場(chǎng)景長(zhǎng)度法O(L)O(1)2最少已知鏈表長(zhǎng)度、思路快速驗(yàn)證快慢指針O(L)O(1)1中等面試首選、要求一次遍歷棧O(L)O(L)1 彈出 n 個(gè)較少展示數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)化思路從復(fù)雜度看長(zhǎng)度法和快慢指針的空間都是 O(1)區(qū)別只在是否允許遍歷兩次。實(shí)際工程里如果鏈表自帶 size長(zhǎng)度法反而最推薦如果是 LeetCode 面試題快慢指針最穩(wěn)妥棧解法適合作為補(bǔ)充答案展示思維寬度。5.2 面試回答順序與復(fù)盤要點(diǎn)我自己做面試官的時(shí)候最反感候選人一句話不說(shuō)直接默寫快慢指針。不是說(shuō)快慢指針不對(duì)而是它太像“背題”。更好的回答節(jié)奏是先從長(zhǎng)度法講起講清楚求長(zhǎng)度、換算正數(shù)、找前驅(qū)這一整套邏輯然后主動(dòng)優(yōu)化“題目要求一次遍歷的話可以用快慢指針讓 fast 先走 n1 步……”如果面試官有興趣再補(bǔ)棧解法。面試結(jié)束后的復(fù)盤重點(diǎn)看三件事是否理解 dummy 存在的意義是否能解釋 fast 為什么走 n1 步是否能準(zhǔn)確說(shuō)出循環(huán)終止條件。這三個(gè)問(wèn)題能答清楚就算代碼寫得慢一點(diǎn)面試官也會(huì)覺得你是真的會(huì)而不是背下來(lái)的。很多候選人背了模板一換數(shù)字就不會(huì)了就是栽在這上面。6. 實(shí)戰(zhàn)排坑刷完這道題之后我總結(jié)的四個(gè)細(xì)節(jié)6.1 坑一返回舊 head 而不是 dummy-next我見過(guò)有人明明新建了 dummy最后卻寫return head;。這代碼在大部分測(cè)試用例里都能過(guò)唯獨(dú) n 等于鏈表長(zhǎng)度時(shí)會(huì)出問(wèn)題head 指向的節(jié)點(diǎn)已經(jīng)被 delete你返回的是一個(gè)懸空指針。C 里這個(gè)行為是未定義的本地可能崩也可能碰巧跑出隨機(jī)值線上就更不可控。正確姿勢(shì)永遠(yuǎn)是ListNode* newHead dummy-next;然后再 delete dummy。注意順序先取 newHead再釋放 dummy這兩個(gè)操作互不影響因?yàn)?newHead 是 dummy 所指向的下一個(gè)節(jié)點(diǎn)釋放 dummy 不會(huì)帶走它。6.2 坑二本地構(gòu)造鏈表時(shí)沒有配套的釋放邏輯LeetCode 的判題環(huán)境不檢查內(nèi)存泄漏但本地調(diào)試時(shí)如果不釋放用 Valgrind 或 AddressSanitizer 一跑就是滿屏報(bào)錯(cuò)。我刷鏈表題的習(xí)慣是寫三個(gè)輔助函數(shù)createList、printList、freeList專門用來(lái)做本地驗(yàn)證。ListNode* createList(const vectorint nums) { ListNode* dummy new ListNode(0); ListNode* cur dummy; for (int num : nums) { cur-next new ListNode(num); cur cur-next; } return dummy-next; } void printList(ListNode* head) { while (head) { cout head-val - ; head head-next; } cout nullptr endl; } void freeList(ListNode* head) { while (head) { ListNode* next head-next; delete head; head next; } }有了這套輔助函數(shù)你可以針對(duì) n1、nL、L1 三種邊界反復(fù)測(cè)既驗(yàn)證算法正確性也讓自己真正意識(shí)到“刪除節(jié)點(diǎn)要釋放內(nèi)存”不是一個(gè)可有可無(wú)的動(dòng)作。6.3 坑三長(zhǎng)度法第二個(gè)循環(huán)的差一問(wèn)題長(zhǎng)度法最常見的問(wèn)題出現(xiàn)在第二個(gè)循環(huán)。如果從 head 出發(fā)很多人會(huì)寫for (int i 1; i length - n 1; i)這個(gè)循環(huán)結(jié)束之后cur 停在待刪節(jié)點(diǎn)本身而不是它的前驅(qū)。于是你不得不額外加一個(gè)變量來(lái)記錄上一個(gè)節(jié)點(diǎn)代碼瞬間變得復(fù)雜。我推薦始終從 dummy 出發(fā)循環(huán)變量從 0 開始循環(huán)次數(shù)是 length - n。這背后的邏輯是dummy 占第 0 個(gè)位置走 length - n 次正好到達(dá)第 length - n 個(gè)節(jié)點(diǎn)也就是待刪節(jié)點(diǎn)的前驅(qū)。每次循環(huán)只做prev prev-next不摻雜任何判斷思路最干凈。6.4 坑四快慢指針的循環(huán)條件想當(dāng)然快慢指針的另一個(gè)高頻錯(cuò)誤是把while (fast ! nullptr)寫成while (fast-next ! nullptr)。乍一看后者似乎是讓 fast 停在最后一個(gè)節(jié)點(diǎn)不再往后多走一步但當(dāng)你讓 fast 先走 n1 步之后如果鏈表長(zhǎng)度恰好是 nfast 已經(jīng)是 nullptr再判斷fast-next就會(huì)解引用空指針直接崩潰。即便鏈表長(zhǎng)度大于 nwhile (fast-next)會(huì)讓 fast 提前一個(gè)位置停止slow 跟著少走一步最終指向待刪節(jié)點(diǎn)而不是前驅(qū)刪除邏輯還是錯(cuò)的。我把結(jié)論說(shuō)直白一點(diǎn)fast 先走 n1 步循環(huán)條件就用while (fast ! nullptr)這是一對(duì)固定搭配不要混搭。這道題我這幾年陸陸續(xù)續(xù)刷過(guò)很多遍每次重新寫都會(huì)發(fā)現(xiàn)自己的指針感又退步了一點(diǎn)。后來(lái)我總結(jié)出一個(gè)習(xí)慣寫代碼前先問(wèn)自己三個(gè)問(wèn)題——鏈表長(zhǎng)度是多少我要?jiǎng)h的節(jié)點(diǎn)的前驅(qū)是誰(shuí)刪的是頭結(jié)點(diǎn)怎么辦這三個(gè)問(wèn)題想清楚長(zhǎng)度法、快慢指針、棧的代碼幾乎都是水到渠成。希望這篇分析能幫你把這道經(jīng)典題的差一邏輯真正刻進(jìn)肌肉記憶下次再遇到鏈表刪除能少踩一個(gè)是一個(gè)。