反轉(zhuǎn)鏈表是算法面試?yán)锍鰣?chǎng)率最高的題目之一LeetCode 206題的評(píng)論區(qū)幾乎成了各家公司面試題的集合地。我第一次刷這題時(shí)覺(jué)得沒(méi)什么難度結(jié)果手寫(xiě)階段指針繞來(lái)繞去寫(xiě)出來(lái)的代碼自己都看不下去。后來(lái)花了一整天把它徹底弄明白才發(fā)現(xiàn)這道題背后藏著鏈表操作最核心的一套基本功。這篇當(dāng)作我Day 4的復(fù)盤(pán)筆記把反轉(zhuǎn)鏈表的迭代法、遞歸法、頭插法以及面試?yán)锍Ｒ?jiàn)的變體題和邊界條件一次性講透。準(zhǔn)備面試的同學(xué)可以照著過(guò)一遍已經(jīng)工作的朋友如果鏈表操作生疏了拿來(lái)溫習(xí)也正合適。1. 面試官到底想考什么——反轉(zhuǎn)鏈表的考點(diǎn)拆解1.1 鏈表的底層結(jié)構(gòu)與反轉(zhuǎn)的本質(zhì)先回到最基礎(chǔ)的問(wèn)題鏈表到底是什么單向鏈表由一個(gè)個(gè)節(jié)點(diǎn)Node通過(guò)引用串起來(lái)每個(gè)節(jié)點(diǎn)至少包含一個(gè)數(shù)據(jù)域和一個(gè)指向下一個(gè)節(jié)點(diǎn)的引用next。頭節(jié)點(diǎn)是鏈表的入口最后一個(gè)節(jié)點(diǎn)的next指向null。數(shù)組在內(nèi)存中是連續(xù)的鏈表則是零散分布的節(jié)點(diǎn)靠指針連接這也是它叫“鏈”表的原因。反轉(zhuǎn)鏈表的操作就是把每個(gè)節(jié)點(diǎn)next指針的方向調(diào)轉(zhuǎn)原來(lái)是1 - 2 - 3 - null反轉(zhuǎn)后變成3 - 2 - 1 - null?？雌饋?lái)就是改幾個(gè)指針但實(shí)際做起來(lái)難點(diǎn)在于“改指針的先后順序”。比如你把1的next從2改成了null那2這個(gè)節(jié)點(diǎn)就徹底找不到了鏈表還沒(méi)反轉(zhuǎn)就已經(jīng)斷了。所以必須先保存后續(xù)節(jié)點(diǎn)再修改當(dāng)前指針最后移動(dòng)指針繼續(xù)處理。這個(gè)“先保存、再修改、再移動(dòng)”的節(jié)奏不只是反轉(zhuǎn)鏈表的核心也是幾乎所有鏈表操作的核心。面試時(shí)如果考的是節(jié)點(diǎn)定義通常是這樣的public class ListNode { int val; ListNode next; ListNode(int x) { val x; } }寫(xiě)題之前先確認(rèn)數(shù)據(jù)結(jié)構(gòu)不要一上來(lái)就寫(xiě)代碼。很多面試官會(huì)故意把節(jié)點(diǎn)定義放在題目里就是看你會(huì)不會(huì)認(rèn)真讀題。1.2 為什么反轉(zhuǎn)鏈表是面試高頻題第一個(gè)原因它太基礎(chǔ)了基礎(chǔ)到任何語(yǔ)言、任何方向的崗位都可能問(wèn)。后端問(wèn)客戶端問(wèn)甚至一些偏數(shù)據(jù)方向的崗位也會(huì)拿它來(lái)熱場(chǎng)。第二個(gè)原因這道題的實(shí)現(xiàn)非?？简?yàn)代碼嚴(yán)謹(jǐn)性。鏈表操作沒(méi)有數(shù)組那種“天然下標(biāo)”的便利所有訪問(wèn)都靠指針每一步都要想清楚當(dāng)前指針指向誰(shuí)、下一個(gè)該指向誰(shuí)。第三個(gè)原因它給面試官留了足夠多的追問(wèn)空間——迭代寫(xiě)完了可以問(wèn)遞歸遞歸寫(xiě)完了可以問(wèn)能不能把空間復(fù)雜度降到O(1)再往深處引就是快慢指針、回文判斷、區(qū)間反轉(zhuǎn)、K個(gè)一組反轉(zhuǎn)這些經(jīng)典變體。一道題能串起十幾個(gè)考點(diǎn)面試官當(dāng)然愛(ài)用。1.3 面試中這題的三個(gè)隱藏考察點(diǎn)第一邊界條件的處理。輸入空鏈表能不能返回null只有一個(gè)節(jié)點(diǎn)的時(shí)候會(huì)不會(huì)出錯(cuò)這幾乎是鏈表題最容易被扣分的地方。第二空間復(fù)雜度意識(shí)。用遞歸寫(xiě)反轉(zhuǎn)代碼很漂亮但空間復(fù)雜度是O(n)面試官追一句“能不能優(yōu)化到O(1)”如果答不上來(lái)印象分會(huì)掉一大截。第三自測(cè)能力。寫(xiě)完之后能不能主動(dòng)舉例驗(yàn)證而不是等著面試官報(bào)測(cè)試用例這三個(gè)點(diǎn)做好哪怕代碼不夠簡(jiǎn)潔面試官給你的評(píng)價(jià)也會(huì)高一個(gè)檔次。2. 迭代法三指針逐步反轉(zhuǎn)2.1 核心思路先保存再改指向再移動(dòng)迭代法最經(jīng)典的寫(xiě)法是維護(hù)三個(gè)指針prev前一個(gè)節(jié)點(diǎn)、curr當(dāng)前節(jié)點(diǎn)、next當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。每一步操作濃縮成三句話先用next保存curr的下一個(gè)節(jié)點(diǎn)防止丟失把curr的next改為prev讓當(dāng)前節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)三個(gè)指針整體后移繼續(xù)處理下一個(gè)節(jié)點(diǎn)。用一個(gè)生活化類比來(lái)理解一排人排隊(duì)每個(gè)人原本都看著自己前面那個(gè)人的后腦勺next指向隊(duì)列前方?，F(xiàn)在要整隊(duì)反方向站你得讓每個(gè)人先記住他原來(lái)前面是誰(shuí)保存next再轉(zhuǎn)身看向原來(lái)后面那個(gè)人反轉(zhuǎn)指針然后自己往隊(duì)尾方向走一步繼續(xù)傳達(dá)指令。任何人轉(zhuǎn)身之前都必須先記住原來(lái)的“下一個(gè)人”否則隊(duì)伍就斷了。這個(gè)過(guò)程中還有一個(gè)關(guān)鍵的理解點(diǎn)prev的初始值是null。為什么不是head因?yàn)榉崔D(zhuǎn)后原鏈表的頭節(jié)點(diǎn)會(huì)變成尾節(jié)點(diǎn)而尾節(jié)點(diǎn)的next必須指向null。如果你把prev初始化為head最后鏈表會(huì)形成環(huán)測(cè)試直接超時(shí)。很多初學(xué)者的第一個(gè)bug就出在這里。2.2 代碼實(shí)現(xiàn)與逐行講解public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode next curr.next; // 先保存下一個(gè)節(jié)點(diǎn) curr.next prev; // 反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)的指針 prev curr; // prev 前移 curr next; // curr 前移 } return prev; // 循環(huán)結(jié)束時(shí) prev 就是新鏈表的頭 }逐行拆解一下執(zhí)行過(guò)程。初始時(shí)prev為nullcurr為原鏈表頭head。假設(shè)原鏈表是1 - 2 - 3 - null第一次循環(huán)next保存21.next改為null鏈表斷成null - 1同時(shí)2 - 3還連著prev移到1curr移到2。第二次循環(huán)next保存32.next改為1鏈表變成null - 1 - 2prev移到2curr移到3。第三次循環(huán)next保存null3.next改為2鏈表變成null - 1 - 2 - 3prev移到3curr變成null循環(huán)結(jié)束。返回prev新鏈表的頭就是3。這段代碼還有一個(gè)可以深挖的點(diǎn)叫“循環(huán)不變式”。每次循環(huán)開(kāi)始前prev指向“已經(jīng)反轉(zhuǎn)好的鏈表的頭”curr指向“接下來(lái)待處理鏈表的頭”。這個(gè)不變量貫穿整個(gè)循環(huán)所以你最后可以放心返回prev。理解這個(gè)比背代碼有用得多因?yàn)槊嬖嚬贂?huì)換各種方式考你只有真正理解指針狀態(tài)變化的人才能應(yīng)對(duì)。2.3 復(fù)雜度分析為什么是O(n)時(shí)間復(fù)雜度看循環(huán)次數(shù)鏈表的每個(gè)節(jié)點(diǎn)都會(huì)進(jìn)入一次循環(huán)。循環(huán)里做的事情是常數(shù)規(guī)模的——保存引用、修改引用、移動(dòng)引用沒(méi)有嵌套循環(huán)所以時(shí)間復(fù)雜度是O(n)n是鏈表長(zhǎng)度?？臻g復(fù)雜度看額外開(kāi)銷只用了prev、curr、next三個(gè)固定變量沒(méi)有開(kāi)數(shù)組、沒(méi)有遞歸調(diào)用棧所以空間復(fù)雜度是O(1)。這里有一個(gè)細(xì)節(jié)值得注意如果鏈表有環(huán)上面的循環(huán)會(huì)不會(huì)死循環(huán)會(huì)的。curr會(huì)一直在環(huán)里轉(zhuǎn)永遠(yuǎn)到不了null。所以面試時(shí)如果題目沒(méi)有明確說(shuō)鏈表無(wú)環(huán)可以先問(wèn)一句“鏈表有沒(méi)有環(huán)”或者在代碼里主動(dòng)加入環(huán)檢測(cè)。這些是后面的變體題這里先不展開(kāi)。2.4 邊界條件與易錯(cuò)點(diǎn)邊界條件本質(zhì)上就三種但漏掉任何一種都可能翻車空鏈表head為null循環(huán)一次都不執(zhí)行返回prev也就是null正確。單節(jié)點(diǎn)head.next為null第一次循環(huán)后prev指向唯一節(jié)點(diǎn)curr為null返回該節(jié)點(diǎn)正確。兩個(gè)節(jié)點(diǎn)手動(dòng)推一遍1和2反轉(zhuǎn)后返回2別寫(xiě)錯(cuò)返回變量。最容易犯的錯(cuò)有兩個(gè)。第一個(gè)是返回curr而不是prev。循環(huán)結(jié)束時(shí)curr一定是null返回curr就是返回空鏈表。這個(gè)錯(cuò)我見(jiàn)過(guò)太多人犯因?yàn)檠h(huán)里一直在移動(dòng)curr潛意識(shí)里覺(jué)得curr才是結(jié)果。第二個(gè)是忘記用next保存后繼節(jié)點(diǎn)直接做curr.next prev結(jié)果下一個(gè)節(jié)點(diǎn)找不到了鏈表從中間斷掉。提示寫(xiě)完后把“返回prev”這個(gè)動(dòng)作作為檢查點(diǎn)想想循環(huán)結(jié)束時(shí)prev指向什么、curr指向什么。想清楚這兩個(gè)指針的最終狀態(tài)返回值就不會(huì)寫(xiě)錯(cuò)。3. 遞歸法從最后一個(gè)節(jié)點(diǎn)往前想3.1 遞歸的思路把大問(wèn)題拆成小問(wèn)題迭代法是從鏈表頭開(kāi)始一個(gè)一個(gè)改遞歸法換一個(gè)視角反轉(zhuǎn)1 - 2 - 3 - null可以拆成“反轉(zhuǎn)2 - 3 - null再把1放到最后面”。而反轉(zhuǎn)2 - 3 - null又可以拆成“反轉(zhuǎn)3 - null再把2放到最后面”。一直拆到不能再拆也就是只剩一個(gè)節(jié)點(diǎn)或者空鏈表。這個(gè)思路用公式寫(xiě)就是如果head為null或者h(yuǎn)ead.next為null返回head否則newHead reverseList(head.next)然后把head放到反轉(zhuǎn)后鏈表的末尾head.next.next head最后把head.next置為null防止成環(huán)。很多人看不懂遞歸反轉(zhuǎn)卡在“head.next.next head”這一步。拆開(kāi)來(lái)看遞歸調(diào)用reverseList(head.next)返回之后newHead是“head的下一個(gè)節(jié)點(diǎn)開(kāi)始反轉(zhuǎn)后形成的鏈表的頭”而head.next此時(shí)指向的節(jié)點(diǎn)正好是反轉(zhuǎn)后鏈表的尾節(jié)點(diǎn)。所以head.next.next head的意思就是把原鏈表的頭節(jié)點(diǎn)接到反轉(zhuǎn)后鏈表的末尾。這個(gè)操作本質(zhì)上就是“把當(dāng)前節(jié)點(diǎn)放到最后”。3.2 完整代碼與手把手思路public ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseList(head.next); head.next.next head; head.next null; return newHead; }我建議第一次學(xué)遞歸反轉(zhuǎn)時(shí)把鏈表長(zhǎng)度縮小到兩個(gè)節(jié)點(diǎn)比如1 - 2 - null手動(dòng)走一遍調(diào)用reverseList(1)1.next不為null進(jìn)入遞歸調(diào)用reverseList(2)reverseList(2)2.next為null直接返回2回到reverseList(1)這一層newHead 2執(zhí)行head.next.next head也就是2.next 1執(zhí)行head.next null也就是1.next null返回newHead即2。此時(shí)鏈表已經(jīng)變成2 - 1 - null。整個(gè)過(guò)程里最關(guān)鍵的是理解遞歸棧的“返回”順序先深入到底再逐層返回并修改指針。只要你把“當(dāng)前層需要做什么”想清楚遞歸的代碼就非常簡(jiǎn)潔。我自己刷題時(shí)凡是遞歸版本的鏈表題都會(huì)先在紙上畫(huà)出遞歸返回的順序再寫(xiě)代碼出錯(cuò)率會(huì)低很多。3.3 遞歸法的空間開(kāi)銷遞歸不是免費(fèi)的。每次遞歸調(diào)用都會(huì)在方法調(diào)用棧上壓入一層棧幀保存當(dāng)前的參數(shù)、局部變量和返回地址。反轉(zhuǎn)一個(gè)n節(jié)點(diǎn)的鏈表遞歸深度就是n空間復(fù)雜度是O(n)。鏈表長(zhǎng)度幾千沒(méi)問(wèn)題但如果鏈表有幾萬(wàn)個(gè)節(jié)點(diǎn)遞歸可能導(dǎo)致棧溢出。這是面試官最常在遞歸版代碼后面追問(wèn)的坑你需要在被問(wèn)之前自己說(shuō)出來(lái)。另一個(gè)細(xì)節(jié)是在Java中遞歸每層棧幀的開(kāi)銷比C稍微小一些但數(shù)量級(jí)一樣是O(n)。不要因?yàn)闇y(cè)試用例比較小就忽略這個(gè)問(wèn)題面試官考的是分析和工程權(quán)衡能力不是“能不能跑過(guò)”。3.4 面試中迭代和遞歸怎么選如果面試官?zèng)]有特別要求我建議先說(shuō)迭代法。理由有三點(diǎn)第一O(1)空間復(fù)雜度更符合工程化思維第二迭代法更接近底層指針操作能展示你對(duì)數(shù)據(jù)結(jié)構(gòu)的掌控第三寫(xiě)出來(lái)更不容易出邊界問(wèn)題。但遞歸也不能完全不準(zhǔn)備因?yàn)槊嬖嚬俸芸赡茏穯?wèn)“你用遞歸怎么實(shí)現(xiàn)”來(lái)考察你的抽象能力。比較穩(wěn)妥的做法是先寫(xiě)迭代AC之后主動(dòng)補(bǔ)一句“這個(gè)題也可以用遞歸實(shí)現(xiàn)但空間復(fù)雜度會(huì)到O(n)”然后把遞歸版本講出來(lái)。這樣既展示了兩種解法也說(shuō)明你知道遞歸的代價(jià)面試官會(huì)覺(jué)得你思路完整。4. 換一種視角頭插法實(shí)現(xiàn)反轉(zhuǎn)4.1 頭插法的思路每次把節(jié)點(diǎn)插到頭部除了三指針迭代和遞歸還有一種思路也值得掌握頭插法。它的想法是重新構(gòu)建一條新鏈表遍歷原始鏈表的每一個(gè)節(jié)點(diǎn)每遇到一個(gè)節(jié)點(diǎn)就把它插入到新鏈表的頭部。最后一個(gè)插入的反而是第一個(gè)節(jié)點(diǎn)天然完成反轉(zhuǎn)。頭插法有兩種寫(xiě)法一種是定義一個(gè)啞節(jié)點(diǎn)dummy另一種是直接定義一個(gè)null的新鏈表頭newHead。我用后者代碼更直觀。這里要注意一個(gè)思維切換點(diǎn)迭代法的視角是“原地反轉(zhuǎn)原鏈表”頭插法的視角是“構(gòu)建一條新鏈表不斷往頭部插入”。雖然代碼長(zhǎng)得像但講出來(lái)的邏輯路線完全不同。面試時(shí)講清楚這個(gè)差異往往比代碼本身更讓面試官認(rèn)同。4.2 代碼實(shí)現(xiàn)public ListNode reverseList(ListNode head) { ListNode newHead null; ListNode curr head; while (curr ! null) { ListNode next curr.next; curr.next newHead; // 當(dāng)前節(jié)點(diǎn)指向新鏈表頭 newHead curr; // 更新新鏈表頭 curr next; } return newHead; }這個(gè)寫(xiě)法其實(shí)和三指針迭代非常像只是把它解釋成“往新鏈表頭部不斷插入”。兩者在內(nèi)存上并沒(méi)有本質(zhì)區(qū)別因?yàn)槎紱](méi)有額外開(kāi)節(jié)點(diǎn)。真正不同的地方在于思考方式頭插法把“反轉(zhuǎn)”重新解釋成“不斷把元素放到最前面”。這個(gè)視角在區(qū)間反轉(zhuǎn)里格外有用因?yàn)閰^(qū)間反轉(zhuǎn)需要“把區(qū)間內(nèi)的節(jié)點(diǎn)逐個(gè)提到區(qū)間頭部”本質(zhì)上就是局部頭插。4.3 三種寫(xiě)法對(duì)比方法時(shí)間復(fù)雜度空間復(fù)雜度核心思想適用場(chǎng)景迭代法三指針O(n)O(1)原地修改指針?lè)较蚴走x面試默認(rèn)遞歸法O(n)O(n)拆子問(wèn)題反向鏈接展示抽象思維頭插法O(n)O(1)構(gòu)建新鏈表頭部插入理解前插邏輯區(qū)間反轉(zhuǎn)常用三種方法的代碼長(zhǎng)度差不多迭代和頭插的空間表現(xiàn)一樣好真正拉開(kāi)差距的是你對(duì)思路的講解是否清晰。面試時(shí)不需要寫(xiě)出全部三種但至少要把其中一種講透其余兩種做到“被問(wèn)到能馬上寫(xiě)出來(lái)”。我在準(zhǔn)備階段會(huì)把三種版本各寫(xiě)兩遍目的是讓大腦形成多條檢索路徑面試時(shí)無(wú)論面試官?gòu)哪膫€(gè)角度切入我都能接住。5. 反轉(zhuǎn)鏈表的變體題面試中的延伸5.1 區(qū)間反轉(zhuǎn)只反轉(zhuǎn)中間一段LeetCode 92題反轉(zhuǎn)從第left個(gè)節(jié)點(diǎn)到第right個(gè)節(jié)點(diǎn)其余部分保持原樣。這題被問(wèn)得非常多因?yàn)閰^(qū)間反轉(zhuǎn)是驗(yàn)證你是否真正理解了反轉(zhuǎn)邏輯而不是背模板的試金石。核心步驟定義一個(gè)啞節(jié)點(diǎn)dummy指向head方便處理left等于1的情況用指針pre走left-1步停在left前一個(gè)節(jié)點(diǎn)從pre.next開(kāi)始進(jìn)行right-left次頭插操作把節(jié)點(diǎn)逐個(gè)提到區(qū)間頭部最后pre.next指向反轉(zhuǎn)后的頭原來(lái)的left節(jié)點(diǎn)的next指向right后面的節(jié)點(diǎn)。可以直接參考這段代碼public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; for (int i 1; i left; i) { pre pre.next; } ListNode cur pre.next; ListNode next cur.next; for (int i 0; i right - left; i) { cur.next next.next; next.next pre.next; pre.next next; next cur.next; } return dummy.next; }這段代碼的循環(huán)內(nèi)部做的是典型的頭插每次把next節(jié)點(diǎn)從cur后面摘下來(lái)插到pre后面也就是當(dāng)前區(qū)間的頭部。重復(fù)right-left次整個(gè)區(qū)間就反轉(zhuǎn)完成。寫(xiě)這題時(shí)最容易漏掉的是啞節(jié)點(diǎn)的使用。如果不加dummyleft等于1時(shí)pre沒(méi)有前驅(qū)節(jié)點(diǎn)整個(gè)代碼會(huì)變得非常別扭。面試時(shí)能用好啞節(jié)點(diǎn)本身就是加分項(xiàng)。5.2 每?jī)蓚€(gè)節(jié)點(diǎn)一組交換LeetCode 24題1 - 2 - 3 - 4變成2 - 1 - 4 - 3。這題的解法跟反轉(zhuǎn)鏈表神似先處理前兩個(gè)節(jié)點(diǎn)的交換再遞歸處理后面的鏈表。交換兩個(gè)節(jié)點(diǎn)時(shí)同樣需要用臨時(shí)變量保存下一個(gè)節(jié)點(diǎn)不然一輪操作后指針就丟了。遞歸寫(xiě)法非常短public ListNode swapPairs(ListNode head) { if (head null || head.next null) return head; ListNode next head.next; head.next swapPairs(next.next); next.next head; return next; }很多同學(xué)做這題時(shí)容易在“交換后怎么接到后面的鏈表”上卡殼。關(guān)鍵是想清楚遞歸返回值和新鏈表頭的關(guān)系。這里swapPairs(next.next)返回的是“從第三個(gè)節(jié)點(diǎn)起兩兩交換后的鏈表的頭”把它接到head.next上再把next.next指向head兩個(gè)節(jié)點(diǎn)的交換就完成了。這和遞歸法反轉(zhuǎn)鏈表用的是同一個(gè)思維模式先處理子問(wèn)題再把當(dāng)前節(jié)點(diǎn)接到正確的位置。5.3 判斷回文鏈表LeetCode 234題判斷一個(gè)鏈表是否回文。常規(guī)做法是先用快慢指針找到中點(diǎn)再把后半段反轉(zhuǎn)然后前半段和反轉(zhuǎn)后的后半段逐個(gè)比較。這題把鏈表找中點(diǎn)、反轉(zhuǎn)鏈表、指針比較三個(gè)基本操作串在一起是反轉(zhuǎn)鏈表最常見(jiàn)的應(yīng)用場(chǎng)景之一。具體步驟快指針每次走兩步慢指針每次走一步快指針到末尾時(shí)慢指針正好在中點(diǎn)。然后從慢指針開(kāi)始反轉(zhuǎn)后半段。接下來(lái)兩個(gè)指針從兩端向中間移動(dòng)逐個(gè)比較節(jié)點(diǎn)值。比較完之后如果你希望不修改原鏈表可以把后半段再反轉(zhuǎn)回去如果面試官?zèng)]有要求通常不需要還原但主動(dòng)說(shuō)一句“我可以把后半段反轉(zhuǎn)回去恢復(fù)原鏈表”會(huì)顯得你考慮周全。熟練之后你會(huì)發(fā)現(xiàn)反轉(zhuǎn)不是目的“比較”“還原”“拼接”才是。面試官出這道題就是想看你能否把反轉(zhuǎn)鏈表這個(gè)工具靈活用到其他問(wèn)題上。5.4 反轉(zhuǎn)鏈表在實(shí)際工程中的應(yīng)用場(chǎng)景面試之外反轉(zhuǎn)鏈表的思路在很多地方都有影子。比如LRU緩存中調(diào)整節(jié)點(diǎn)位置會(huì)涉及鏈表的摘除和重新插入類似頭插法的邏輯比如文本編輯器的撤銷重做底層用鏈表維護(hù)操作序列反向回溯時(shí)本質(zhì)上就是“從后往前”遍歷鏈表再比如路徑回溯類算法中遞歸返回時(shí)需要逐層撤銷選擇和遞歸反轉(zhuǎn)鏈表的“先深入再逐層處理”是同一個(gè)結(jié)構(gòu)。當(dāng)然絕大多數(shù)業(yè)務(wù)開(kāi)發(fā)不會(huì)真的手寫(xiě)反轉(zhuǎn)鏈表這種數(shù)據(jù)結(jié)構(gòu)級(jí)的操作通常被封裝在標(biāo)準(zhǔn)庫(kù)里。但掌握指針操作會(huì)讓你在排查疑難問(wèn)題時(shí)多一層直覺(jué)。尤其是遇到“容器內(nèi)部實(shí)現(xiàn)導(dǎo)致性能退化”這類問(wèn)題時(shí)理解鏈表的內(nèi)存布局和指針變化比只會(huì)調(diào)用API更能精準(zhǔn)定位問(wèn)題。5.5 一道必會(huì)的綜合題K個(gè)一組反轉(zhuǎn)LeetCode 25題K個(gè)一組反轉(zhuǎn)鏈表。這道題把鏈表反轉(zhuǎn)和邊界處理都拉滿了先判斷剩余節(jié)點(diǎn)是否夠K個(gè)不夠就直接返回夠的話反轉(zhuǎn)這一段然后遞歸處理后面的鏈表。很多公司的高頻題里都有它因?yàn)樗粌H考反轉(zhuǎn)還考“分組”這個(gè)概念怎么和遞歸配合。不建議剛學(xué)完基礎(chǔ)反轉(zhuǎn)就硬刷這題先把區(qū)間反轉(zhuǎn)練熟再上手K個(gè)一組。刷的時(shí)候注意兩點(diǎn)一是反轉(zhuǎn)每一段時(shí)要保證末尾節(jié)點(diǎn)正確指向下一段的開(kāi)頭二是判斷剩余節(jié)點(diǎn)是否夠K個(gè)需要先走K步檢查不夠就停。這個(gè)“先探路再操作”的模式在鏈表題里經(jīng)常出現(xiàn)值得單獨(dú)練。6. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄6.1 常見(jiàn)錯(cuò)誤與排查思路我把自己刷題和帶人時(shí)見(jiàn)過(guò)的問(wèn)題整理成一張表錯(cuò)誤現(xiàn)象可能原因排查思路運(yùn)行死循環(huán)反轉(zhuǎn)后存在環(huán)可能某次操作沒(méi)有把next置null檢查head.next null這一步是否遺漏返回結(jié)果是null循環(huán)結(jié)束時(shí)返回了curr而不是prev用兩個(gè)節(jié)點(diǎn)的鏈表手動(dòng)推導(dǎo)一遍反轉(zhuǎn)后鏈表丟失后半段修改指針前沒(méi)有保存next確保每次循環(huán)先執(zhí)行next curr.next遞歸寫(xiě)法棧溢出遞歸深度太高或終止條件寫(xiě)錯(cuò)檢查終止條件是否處理了空和單節(jié)點(diǎn)長(zhǎng)鏈表改用迭代反轉(zhuǎn)結(jié)果順序不對(duì)指針移動(dòng)順序反了畫(huà)圖標(biāo)出每一步的指針位置變化排查鏈表問(wèn)題最忌諱盯著代碼硬看。正確姿勢(shì)是把鏈表縮到最小規(guī)模用紙筆畫(huà)每一步的指針狀態(tài)。畫(huà)三步基本就能定位問(wèn)題。我在面試輔導(dǎo)中見(jiàn)過(guò)很多人看半天代碼看不出問(wèn)題一畫(huà)圖立刻就發(fā)現(xiàn)是自己把prev和curr的賦值順序搞反了。6.2 鏈表題的調(diào)試小技巧第一寫(xiě)一個(gè)打印鏈表的方法。很多鏈表題看不到中間狀態(tài)打印出來(lái)一目了然。我刷題時(shí)經(jīng)常在方法里臨時(shí)加一行System.out.println查看反轉(zhuǎn)到中間某一步的狀態(tài)確認(rèn)邏輯后再刪掉。第二用小規(guī)模數(shù)據(jù)驗(yàn)證?？真湵?、單節(jié)點(diǎn)、兩個(gè)節(jié)點(diǎn)、三個(gè)節(jié)點(diǎn)這四種情況測(cè)過(guò)之后90%的邊界bug能暴露。第三善用啞節(jié)點(diǎn)。處理需要改動(dòng)頭節(jié)點(diǎn)的操作時(shí)定義一個(gè)dummy節(jié)點(diǎn)能讓代碼少很多邊界判斷尤其適合區(qū)間反轉(zhuǎn)這類需要定位前驅(qū)的場(chǎng)景。調(diào)試時(shí)還會(huì)遇到一個(gè)常見(jiàn)的心理陷阱測(cè)試通過(guò)了就覺(jué)得萬(wàn)事大吉。鏈表題真正要驗(yàn)證的往往是你主動(dòng)構(gòu)造的邊界用例而不是系統(tǒng)給的普通用例。比如反轉(zhuǎn)鏈表普通用例是3個(gè)節(jié)點(diǎn)但你一定得手動(dòng)測(cè)一下空鏈表和單節(jié)點(diǎn)這兩個(gè)用例最容易暴露返回值寫(xiě)錯(cuò)的問(wèn)題。6.3 面試現(xiàn)場(chǎng)的經(jīng)驗(yàn)心得這道題在面試?yán)锍霈F(xiàn)頻率極高我在實(shí)際準(zhǔn)備中總結(jié)出幾條經(jīng)驗(yàn)。首先寫(xiě)代碼之前先把思路說(shuō)出來(lái)哪怕只是簡(jiǎn)單一句“我用三個(gè)指針先保存下一個(gè)再改當(dāng)前指針”面試官就能跟著你的節(jié)奏走也會(huì)更寬容你的小錯(cuò)誤。其次寫(xiě)完之后主動(dòng)做一次自測(cè)不要等面試官給用例自己拿一個(gè)鏈表舉例大聲說(shuō)出每一步指針的變化。這個(gè)動(dòng)作極其加分它說(shuō)明你不是在背代碼而是真的理解算法在做什么。最后再提一個(gè)細(xì)節(jié)面試中如果時(shí)間允許把復(fù)雜度分析主動(dòng)說(shuō)出來(lái)時(shí)間復(fù)雜度O(n)、空間復(fù)雜度O(1)大多數(shù)情況下到這里就夠了。如果面試官追問(wèn)“能不能不用遞歸空間”之類的問(wèn)題直接用前面第2節(jié)的迭代法思路回答把遞歸的空間代價(jià)和迭代的O(1)優(yōu)化講清楚即可。我個(gè)人在實(shí)際操作中的體會(huì)是反轉(zhuǎn)鏈表這道題不難但極其適合作為鏈表題目的起點(diǎn)因?yàn)樗阎羔槻僮鳌⑦吔缣幚?、遞歸思維三個(gè)最核心的東西都包含了。刷完這題之后我建議你立刻把區(qū)間反轉(zhuǎn)、兩兩交換、回文鏈表這三道變體刷一遍你會(huì)發(fā)現(xiàn)它們之間有很多共通的地方。等這些題都掌握了再看K個(gè)一組反轉(zhuǎn)也不會(huì)覺(jué)得離譜。如果你手邊正好有鏈表題做得吃力反轉(zhuǎn)鏈表就是你最應(yīng)該死磕的那塊基石。