要說(shuō)面試?yán)锍霈F(xiàn)頻率最高的鏈表題反轉(zhuǎn)鏈表排第二估計(jì)沒(méi)誰(shuí)敢排第一。我當(dāng)年準(zhǔn)備校招的時(shí)候第一次看到這道題內(nèi)心是有點(diǎn)懵的——明明代碼就那么幾行為什么一上手不是段錯(cuò)誤就是死循環(huán)后來(lái)刷多了才明白這道題考察的根本不是“能不能背出答案”而是你是不是真的理解指針是怎么把一個(gè)節(jié)點(diǎn)串起來(lái)的以及改動(dòng)指針?lè)较驎r(shí)哪些瞬間會(huì)丟節(jié)點(diǎn)。這篇就用C語(yǔ)言把劍指 Offer 24 講透。核心內(nèi)容包含三種解法——迭代法、遞歸法、頭插法——以及我在本地調(diào)試時(shí)踩過(guò)的各種邊界條件的坑。不管你是剛接觸鏈表的小白還是正在沖刺面試的求職者這篇文章的目標(biāo)只有一個(gè)讓你看完之后能獨(dú)立手寫出這段代碼并且敢在面試官面前講清楚每一步在干什么。1. 為什么面試官都愛(ài)考這道題一次考察三種底層能力很多新手不理解反轉(zhuǎn)鏈表這么“簡(jiǎn)單”的題為什么能成為劍指 Offer 的高頻題。我在準(zhǔn)備面試階段刷了上百道題之后最大的體會(huì)是這道題表面上考的是鏈表翻轉(zhuǎn)實(shí)際上考的是三件更底層的本事——指針操作的手感、邊界條件的敏感度、遞歸思想的熟練度。這三個(gè)能力恰恰是做任何 C/C 項(xiàng)目都繞不開的基本功。1.1 鏈表結(jié)構(gòu)體定義與基本打印邏輯先把最基礎(chǔ)的準(zhǔn)備做扎實(shí)。C語(yǔ)言里單鏈表的節(jié)點(diǎn)定義幾乎是固定的面試時(shí)直接默寫struct ListNode { int val; struct ListNode *next; };光有節(jié)點(diǎn)還不夠我習(xí)慣先在本地把“打印鏈表”這個(gè)輔助函數(shù)寫好。別小看這個(gè)動(dòng)作調(diào)試鏈表題時(shí)你每次都靠它確認(rèn)反轉(zhuǎn)結(jié)果對(duì)不對(duì)省下的時(shí)間遠(yuǎn)比寫的幾分鐘多。void printList(struct ListNode *head) { struct ListNode *cur head; while (cur ! NULL) { printf(%d , cur-val); cur cur-next; } printf(\n); }創(chuàng)建一條簡(jiǎn)單測(cè)試鏈表struct ListNode* createTestList() { struct ListNode *n1 (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *n2 (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *n3 (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *n4 (struct ListNode*)malloc(sizeof(struct ListNode)); n1-val 1; n1-next n2; n2-val 2; n2-next n3; n3-val 3; n3-next n4; n4-val 4; n4-next NULL; return n1; }這段測(cè)試代碼看起來(lái)很笨但它對(duì)初學(xué)者的好處是每個(gè)節(jié)點(diǎn)的內(nèi)存都清清楚楚你能直觀看到指針之間是怎么連接的。很多搞不懂反轉(zhuǎn)的人不是不理解算法而是根本不熟悉鏈表的“物理結(jié)構(gòu)”。1.2 這道題在面試題體系中的“地基”位置反轉(zhuǎn)鏈表之所以被反復(fù)考還因?yàn)樗呛芏鄰?fù)雜鏈表題的基礎(chǔ)零件。你不信的話可以想想這幾道題整個(gè)鏈表反轉(zhuǎn)、反轉(zhuǎn)鏈表的前N個(gè)節(jié)點(diǎn)、區(qū)間反轉(zhuǎn)、K個(gè)一組反轉(zhuǎn)鏈表、回文鏈表判斷……這些題的核心思想都建立在單鏈表反轉(zhuǎn)這一個(gè)操作上。拿K個(gè)一組反轉(zhuǎn)來(lái)舉例它其實(shí)就是在鏈表上分段做反轉(zhuǎn)每段的內(nèi)部反轉(zhuǎn)方法和劍指 Offer 24一模一樣。也就是說(shuō)如果你能把這個(gè)基礎(chǔ)版寫得既快又對(duì)后面做進(jìn)階題時(shí)你只需要把注意力放在“每一段的邊界怎么銜接”而不用再糾結(jié)反轉(zhuǎn)本身怎么寫。地基打得穩(wěn)往上蓋樓才不慌。我自己的建議是練習(xí)時(shí)不要只滿足于“調(diào)通了”而是要把迭代法、遞歸法、頭插法都寫一遍并且每個(gè)版本都講得出“為什么這樣寫”。下面幾個(gè)章節(jié)我分別把三種解法拆開聊。2. 迭代法三個(gè)指針輪流“調(diào)頭”一步步把箭頭掰過(guò)來(lái)迭代法是我面試時(shí)最優(yōu)先寫的解法。理由很簡(jiǎn)單時(shí)間復(fù)雜度 O(n)、空間復(fù)雜度 O(1)思路直白不容易寫崩。它本質(zhì)上做的一件事是遍歷鏈表的過(guò)程中逐個(gè)把每個(gè)節(jié)點(diǎn)的 next 指向前一個(gè)節(jié)點(diǎn)同時(shí)用額外的指針保住“下一個(gè)要處理的節(jié)點(diǎn)”。2.1 三指針?biāo)悸放c代碼實(shí)現(xiàn)核心操作可以概括成一句話prev 指向當(dāng)前節(jié)點(diǎn)的前一個(gè)cur 指向當(dāng)前節(jié)點(diǎn)next 暫存 cur 原本的下一個(gè)節(jié)點(diǎn)。每輪循環(huán)把 cur-next 改成 prev然后三個(gè)指針集體往前挪一格。struct ListNode* reverseList_iterative(struct ListNode* head) { struct ListNode *prev NULL; struct ListNode *cur head; struct ListNode *next NULL; while (cur ! NULL) { next cur-next; // 先保存下一個(gè)節(jié)點(diǎn)防止斷鏈 cur-next prev; // 當(dāng)前節(jié)點(diǎn)掉頭指向前一個(gè) prev cur; // prev 前移 cur next; // cur 前移 } return prev; }這里最需要注意的是next cur-next;這一行。我第一次寫的時(shí)候漏掉了它直接把cur-next prev寫上去結(jié)果鏈表從第一個(gè)節(jié)點(diǎn)開始就斷掉了——因?yàn)樵瓉?lái) cur-next 指的那個(gè)節(jié)點(diǎn)沒(méi)有任何變量還指向它誰(shuí)也找不回去了。你可以把鏈表想象成一列手拉手的人現(xiàn)在第一個(gè)人要回頭牽住身后的人那就必須先用另一只手拉住第二個(gè)人否則第二個(gè)人就掉隊(duì)了。2.2 為什么 prev 初始化為 NULL 而不是 head很多初學(xué)者會(huì)問(wèn)prev 為什么不初始化為 head我先不直接回答請(qǐng)你想象一下鏈表反轉(zhuǎn)完之后原來(lái)第一個(gè)節(jié)點(diǎn)的 next 應(yīng)該指向誰(shuí)答案是 NULL因?yàn)樗兂闪诵碌奈补?jié)點(diǎn)。所以 prev 一開始就是 NULL當(dāng)循環(huán)走到最后時(shí)prev 恰好會(huì)停在原來(lái)的最后一個(gè)節(jié)點(diǎn)上而且這個(gè)節(jié)點(diǎn)的 next 已經(jīng)被修改為它的前一個(gè)節(jié)點(diǎn)沒(méi)有殘留的野指針。另外prev 從 NULL 開始還能順帶處理一個(gè)特殊情況如果傳入的是一個(gè)空鏈表head 本身是 NULL循環(huán)一次都不執(zhí)行直接返回 prev也就是 NULL。這個(gè)寫法干凈利落地把空鏈表和單節(jié)點(diǎn)鏈表的情況一并解決了。單節(jié)點(diǎn)鏈表也是同理cur-next 指向 NULL反轉(zhuǎn)后還是那一個(gè)節(jié)點(diǎn)不會(huì)出問(wèn)題。2.3 本地完整測(cè)試把算法跑起來(lái)才算學(xué)會(huì)光看代碼不運(yùn)行和沒(méi)學(xué)區(qū)別不大。我把測(cè)試代碼補(bǔ)全你復(fù)制到本地就能看到效果int main() { struct ListNode *head createTestList(); printf(反轉(zhuǎn)前: ); printList(head); struct ListNode *reversed reverseList_iterative(head); printf(反轉(zhuǎn)后: ); printList(reversed); return 0; }輸出結(jié)果應(yīng)該是反轉(zhuǎn)前: 1 2 3 4 反轉(zhuǎn)后: 4 3 2 1我建議你把printList加進(jìn)循環(huán)里每反轉(zhuǎn)一步打印一次當(dāng)前鏈表狀態(tài)。這樣你能親眼看到節(jié)點(diǎn)一個(gè)接一個(gè)“掉頭”的過(guò)程比單純盯著腦內(nèi)推演要直觀得多。我當(dāng)時(shí)就是這么干的打印幾次之后再也沒(méi)忘記過(guò)三指針的移動(dòng)順序。2.4 一個(gè)常見的筆誤cur 和 next 的賦值順序我見過(guò)不少人包括我自己早期把循環(huán)體寫成了這樣next cur-next; cur-next prev; next cur; // 筆誤應(yīng)該是 prev cur prev next; // 筆誤順序亂了這種錯(cuò)的離譜的寫法表面上看起來(lái)邏輯很“像”跑起來(lái)卻會(huì)得到完全不同的結(jié)果甚至死循環(huán)。我的經(jīng)驗(yàn)是三指針移動(dòng)的時(shí)候眼睛要盯著“誰(shuí)應(yīng)該成為新的 prev誰(shuí)應(yīng)該成為新的 cur”。記住一個(gè)口訣先斷后接再人齊步走——先處理 cur-next 的指向再用 next 帶著 cur 往前走prev 緊跟其后。3. 遞歸法讓指針在“原路返回”的過(guò)程中回頭遞歸解法在代碼量上比迭代法還要短但理解門檻高不少。很多教程直接甩代碼然后說(shuō)“這個(gè)遞歸壓棧再?gòu)棗＞秃昧恕甭牰艘仓皇撬贫嵌?。這一節(jié)我會(huì)用兩種遞歸寫法來(lái)拆重點(diǎn)講清楚每一步回溯時(shí)到底發(fā)生了什么。3.1 理解遞歸的關(guān)鍵先遞到鏈尾再歸中改指向先看最經(jīng)典的遞歸寫法struct ListNode* reverseList_recursive(struct ListNode* head) { if (head NULL || head-next NULL) { return head; } struct ListNode *newHead reverseList_recursive(head-next); head-next-next head; head-next NULL; return newHead; }這段代碼的核心邏輯只有兩行head-next-next head;是把當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的 next 指回當(dāng)前節(jié)點(diǎn)也就是完成一次“反向鉤連”。head-next NULL;是為了讓當(dāng)前節(jié)點(diǎn)當(dāng)前處于鏈表尾部相對(duì)回溯過(guò)程而言時(shí)不再指向原來(lái)的下一個(gè)節(jié)點(diǎn)防止形成環(huán)。許多人的困惑在于“newHead 到底是從哪來(lái)的”答案來(lái)自遞歸的終止條件當(dāng)遞歸遞到鏈表的最后一個(gè)節(jié)點(diǎn)時(shí)head-next NULL直接返回這個(gè)節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)就是整個(gè)鏈表反轉(zhuǎn)后的新頭節(jié)點(diǎn)。它會(huì)被一層層原封不動(dòng)地傳回去所以代碼里return newHead;是一條“接力棒”路徑不是在每層生成新東西。3.2 一條四節(jié)點(diǎn)鏈表的手推全過(guò)程我們拿 1→2→3→4 來(lái)走一遍reverseList_recursive(1) 進(jìn)入head11-next 不是 NULL調(diào)用 reverseList_recursive(2)reverseList_recursive(2) 進(jìn)入head22-next 不是 NULL調(diào)用 reverseList_recursive(3)reverseList_recursive(3) 進(jìn)入head33-next 不是 NULL調(diào)用 reverseList_recursive(4)reverseList_recursive(4) 進(jìn)入head44-next 是 NULL返回 4到這里“遞”的過(guò)程結(jié)束開始“歸”的過(guò)程回到調(diào)用者 head3 的那一層head-next是 4執(zhí)行4-next 3再把3-next NULL返回 newHead4回到調(diào)用者 head2 的那一層此時(shí) 3 的 next 已經(jīng)變成 NULL但 head-next 仍然指向 3所以執(zhí)行3-next 2再把2-next NULL返回 newHead4回到調(diào)用者 head1 的那一層此時(shí) 2 的 next 已經(jīng)是 NULL但 head-next 仍然指向 2執(zhí)行2-next 1再把1-next NULL返回 newHead4最后從函數(shù)外面拿到的 newHead 就是節(jié)點(diǎn) 4從 4 出發(fā)依次是 3、2、1反轉(zhuǎn)完成。這個(gè)過(guò)程我建議你也親手在紙上畫一遍箭頭改來(lái)改去的樣子很像在做手工折紙——每次把折好的方向調(diào)轉(zhuǎn)一次。畫過(guò)一遍之后你對(duì)遞歸的理解會(huì)比背十遍代碼都深刻。3.3 遞歸解法版本二自頂向下返回值攜帶新頭還有另一種遞歸寫法它的思路是“把當(dāng)前節(jié)點(diǎn)放到已反轉(zhuǎn)鏈表的頭部”方向是從前往后處理。這種寫法稍微繞一點(diǎn)但對(duì)理解遞歸返回值很有幫助struct ListNode* reverseList_recursive2(struct ListNode* head) { return reverseHelper(head, NULL); } struct ListNode* reverseHelper(struct ListNode* cur, struct ListNode* prev) { if (cur NULL) { return prev; } struct ListNode *next cur-next; cur-next prev; return reverseHelper(next, cur); }這個(gè)版本本質(zhì)上是用遞歸的形式做了迭代法的事情把 prev 作為參數(shù)一路傳遞下去當(dāng)前節(jié)點(diǎn) cur 的 next 直接改為 prev然后遞歸處理原來(lái)的 next 節(jié)點(diǎn)。它避免了顯式寫循環(huán)但又和迭代法的思路完全一致。面試時(shí)如果你的遞歸版寫得夠熟練也可以順帶提一句這個(gè)自頂向下的寫法展示你對(duì)遞歸和迭代關(guān)系的理解。3.4 遞歸和迭代怎么選一個(gè)務(wù)實(shí)的判斷標(biāo)準(zhǔn)我自己的選擇標(biāo)準(zhǔn)很樸素如果只是解這道題用迭代如果聊到遞歸思想用版本一如果想展示對(duì)“遞歸攜帶狀態(tài)”的掌握可以用版本二。但必須提醒你一個(gè)實(shí)際問(wèn)題遞歸版本在鏈表很長(zhǎng)的時(shí)候會(huì)有風(fēng)險(xiǎn)。C語(yǔ)言的?？臻g有限鏈表長(zhǎng)度達(dá)到幾十萬(wàn)甚至上百萬(wàn)節(jié)點(diǎn)時(shí)遞歸深度過(guò)大會(huì)導(dǎo)致棧溢出。所以面試場(chǎng)景下如果題目沒(méi)有特別說(shuō)明“允許遞歸”我建議默認(rèn)先給迭代解再把遞歸解作為補(bǔ)充方案講解。這樣既保證了代碼的健壯性又展示了你對(duì)兩種思路都吃得透。4. 頭插法與邊界條件從 Dummy Node 到空鏈表所有坑一次排完第三類常見解法是“頭插法”。它的思路是新建一個(gè)啞巴節(jié)點(diǎn)dummy node作為哨兵遍歷原鏈表把每個(gè)節(jié)點(diǎn)拆下來(lái)插入到 dummy 節(jié)點(diǎn)之后。最終dummy-next 就是反轉(zhuǎn)后的新鏈表頭。4.1 頭插法代碼實(shí)現(xiàn)struct ListNode* reverseList_headInsert(struct ListNode* head) { struct ListNode dummy; dummy.next NULL; struct ListNode *cur head; while (cur ! NULL) { struct ListNode *next cur-next; // 暫存剩余鏈表 cur-next dummy.next; // 當(dāng)前節(jié)點(diǎn)指向新鏈表頭 dummy.next cur; // 更新新鏈表頭為當(dāng)前節(jié)點(diǎn) cur next; // 繼續(xù)處理剩余鏈表 } return dummy.next; }注意這里的dummy我是直接定義在棧上的結(jié)構(gòu)體變量而不是用 malloc 分配。原因很簡(jiǎn)單這個(gè)節(jié)點(diǎn)的唯一作用是提供“插入位置的前驅(qū)”不需要長(zhǎng)期存活用完即棄。用棧上變量還能省掉手動(dòng) free 的麻煩代碼也更干凈。如果你喜歡也可以用 malloc 分配一個(gè)struct ListNode *dummy (struct ListNode *)malloc(sizeof(struct ListNode));但記得在返回前 free 掉否則就有內(nèi)存泄漏。4.2 頭插法的適用場(chǎng)景理解它的“原型”反而更好進(jìn)階說(shuō)實(shí)話單就這道題而言頭插法不是主流答案。但理解頭插法對(duì)后續(xù)很多題目幫助很大。舉個(gè)例子經(jīng)典的兩兩交換鏈表節(jié)點(diǎn)、重排鏈表等問(wèn)題都需要“從原鏈表拆除一個(gè)節(jié)點(diǎn)再插到另一個(gè)位置”的能力。頭插法練熟了你會(huì)形成一種“拆裝節(jié)點(diǎn)”的肌肉記憶——先存 next再修改指針再移動(dòng) cur。而且頭插法有一個(gè)迭代法不具備的心智模型它在持續(xù)構(gòu)建“一段已經(jīng)反轉(zhuǎn)好的新鏈表”新鏈表的頭始終在 dummy-next。這種“邊遍歷邊構(gòu)建新鏈表”的思維也是鏈表排序題如插入排序的底層邏輯。所以即使不常用我也強(qiáng)烈建議你寫一遍。4.3 邊界條件清單空鏈表、單節(jié)點(diǎn)、雙節(jié)點(diǎn)、大鏈表我最近在做題目復(fù)盤時(shí)把邊界條件整理成了一個(gè)小清單每次寫完反轉(zhuǎn)代碼都用它來(lái)自檢場(chǎng)景預(yù)期結(jié)果容易踩的坑空鏈表 headNULL返回 NULL循環(huán)不會(huì)執(zhí)行注意返回值別寫成野指針單節(jié)點(diǎn)鏈表返回原節(jié)點(diǎn)確保該節(jié)點(diǎn)的 next 變成 NULL雙節(jié)點(diǎn)鏈表返回原第二個(gè)節(jié)點(diǎn)注意原頭節(jié)點(diǎn)的 next 必須置空長(zhǎng)鏈表全部倒序防止遞歸版本棧溢出優(yōu)先用迭代鏈表有環(huán)理論上不會(huì)有死循環(huán)可思考該算法為什么能檢測(cè)出環(huán)其實(shí)不能最后一行“鏈表有環(huán)”雖然在題目約定下不會(huì)出現(xiàn)但我在實(shí)際面試追問(wèn)環(huán)節(jié)被問(wèn)過(guò)“如果鏈表帶環(huán)會(huì)怎樣”。我當(dāng)時(shí)答得不夠好這里提醒你迭代法面對(duì)有環(huán)節(jié)點(diǎn)時(shí)cur 永遠(yuǎn)不會(huì)走到 NULL循環(huán)不會(huì)結(jié)束。所以在真實(shí)工程中如果你不確定鏈表是否干凈先做環(huán)檢測(cè)再說(shuō)。4.4 內(nèi)存管理的細(xì)節(jié)C語(yǔ)言版本絕不能漏掉的問(wèn)題這道題用 C 語(yǔ)言寫還有一個(gè)需要留意的點(diǎn)反轉(zhuǎn)操作本身不改變節(jié)點(diǎn)的數(shù)量也不會(huì)新分配節(jié)點(diǎn)。所以在純反轉(zhuǎn)場(chǎng)景下你不需要考慮 free 每個(gè)節(jié)點(diǎn)。但如果你的測(cè)試代碼里像上面的 createTestList 一樣用 malloc 建了一批節(jié)點(diǎn)那在測(cè)試結(jié)束后最好把它們都 free 掉避免內(nèi)存泄漏。調(diào)試階段的習(xí)慣也很重要printList之后遍歷完鏈表注意別對(duì)已經(jīng) free 的節(jié)點(diǎn)再訪問(wèn)。我曾經(jīng)因?yàn)橄?free 再 print 的順序搞反直接觸發(fā)了“use after free”排查了半天才反應(yīng)過(guò)來(lái)。后來(lái)我把輔助函數(shù)都統(tǒng)一成“先打印、后釋放”的順序再也沒(méi)出過(guò)這類問(wèn)題。5. 面試現(xiàn)場(chǎng)的完整應(yīng)對(duì)思路從白板畫圖到 Bug 復(fù)現(xiàn)算法題刷得再多面試時(shí)如果表達(dá)不清楚效果都會(huì)打折扣。我在經(jīng)歷了幾輪真正的技術(shù)面之后最大的感受是面試官真正想看的不是答案而是你思考問(wèn)題的路徑。所以反轉(zhuǎn)鏈表這道題準(zhǔn)備的不應(yīng)該是“背代碼”而是一套可以現(xiàn)場(chǎng)展示的解題流程。5.1 動(dòng)筆之前的固定動(dòng)作先畫鏈表再標(biāo)指針我每次面試遇到鏈表題都會(huì)先畫一個(gè)至少包含三到四個(gè)節(jié)點(diǎn)的鏈表圖節(jié)點(diǎn)用方框表示next 用箭頭表示。然后在這條鏈表上方標(biāo)出三個(gè)位置prev、cur、next。接著逐步演示第一輪循環(huán)怎么改箭頭方向第二輪怎么移動(dòng)指針。這個(gè)動(dòng)作看似浪費(fèi)時(shí)間實(shí)際上有雙倍收益一方面幫你自己理清思路減少寫代碼時(shí)的手忙腳亂另一方面讓面試官看到你是“有結(jié)構(gòu)地思考”而不是“硬背答案”。我遇到好幾個(gè)面試官在我畫圖時(shí)頻頻點(diǎn)頭后面追問(wèn)的問(wèn)題也明顯友善了很多。5.2 一套可以現(xiàn)場(chǎng)復(fù)現(xiàn)的自測(cè)用例寫完代碼之后千萬(wàn)別直接說(shuō)“寫完了”。我在最后一次找工作時(shí)學(xué)到的是主動(dòng)提出“跑幾個(gè)用例驗(yàn)證一下”。面試官通常會(huì)讓你口頭走一遍你可以按這個(gè)順序來(lái)空鏈表head 是 NULL循環(huán)體不執(zhí)行直接返回 NULL。單節(jié)點(diǎn)一系列 1→NULL循環(huán)執(zhí)行一次返回原節(jié)點(diǎn)。普通鏈表1→2→3走完三輪。如果面試官讓你在白板上寫完整的 main 測(cè)試也完全不用慌把 createTestList 和 printList 寫出來(lái)就行。能當(dāng)場(chǎng)寫出測(cè)試代碼是很加分的行為因?yàn)檫@表明你不只會(huì)寫算法還知道怎么驗(yàn)證結(jié)果。5.3 進(jìn)階追問(wèn)的延伸思考反轉(zhuǎn)前 K 個(gè)節(jié)點(diǎn)與區(qū)間反轉(zhuǎn)面試官很可能在你寫出基礎(chǔ)反轉(zhuǎn)后追問(wèn)一句“那反轉(zhuǎn)前 K 個(gè)節(jié)點(diǎn)你會(huì)嗎”這個(gè)問(wèn)題其實(shí)是劍指 Offer 24 的直接變體。思路和迭代法一致只是只循環(huán) K 次反轉(zhuǎn)前 K 個(gè)節(jié)點(diǎn)。反轉(zhuǎn)完成后原來(lái)的第 K1 個(gè)節(jié)點(diǎn)需要接在鏈表末尾所以代碼里要保存一下原鏈表的“后續(xù)部分”struct ListNode* reverseK(struct ListNode* head, int k) { struct ListNode *prev NULL; struct ListNode *cur head; struct ListNode *next NULL; for (int i 0; i k cur ! NULL; i) { next cur-next; cur-next prev; prev cur; cur next; } // 此時(shí) head 是反轉(zhuǎn)后的尾節(jié)點(diǎn)它的 next 應(yīng)接上 cur if (head ! NULL) { head-next cur; } return prev; }然后如果把這個(gè)基礎(chǔ)版再升級(jí)成區(qū)間反轉(zhuǎn)比如反轉(zhuǎn)第 m 到第 n 個(gè)節(jié)點(diǎn)思路就是先找到前驅(qū)節(jié)點(diǎn)然后對(duì)區(qū)間內(nèi)部做同樣的反轉(zhuǎn)再把前驅(qū)和區(qū)間尾接好。你會(huì)發(fā)現(xiàn)所有升級(jí)版的核心零件還是今天這道題。這也就是我開頭說(shuō)的“地基”含義。5.4 我自己刷這道題的真實(shí)體會(huì)回頭來(lái)看反轉(zhuǎn)鏈表是我刷題階段“從背答案到懂答案”的轉(zhuǎn)折點(diǎn)。剛開始我只能默寫迭代法面試被問(wèn)“為什么 next 要先保存”時(shí)我只會(huì)說(shuō)“怕斷鏈”但根本講不清斷鏈的瞬間發(fā)生了什么。后來(lái)我強(qiáng)迫自己把遞歸版也手推三遍又在本地把三種解法全部跑通并打印每一步之后遇到任何鏈表反轉(zhuǎn)變體我都不慌。這里也分享一個(gè)小技巧學(xué)鏈表題時(shí)不要只用眼睛看一定要?jiǎng)邮执蛴?。我見過(guò)許多人連printList都不會(huì)寫就來(lái)刷鏈表題效率低很多。先把輔助函數(shù)準(zhǔn)備好的習(xí)慣養(yǎng)成后面刷 K 個(gè)一組反轉(zhuǎn)、回文鏈表時(shí)都不會(huì)吃虧。另外我也想說(shuō)面試時(shí)如果一時(shí)緊張忘了代碼不妨先從畫圖開始。把箭頭一個(gè)個(gè)掰過(guò)去代碼自然就順著畫出來(lái)了。這個(gè)動(dòng)作我已經(jīng)重復(fù)無(wú)數(shù)遍每次仍然管用。反轉(zhuǎn)鏈表這道題說(shuō)難不難說(shuō)容易也不容易。真正把它吃透的標(biāo)準(zhǔn)不是“能復(fù)制答案”而是“指針在每一輪循環(huán)里指向誰(shuí)、下一步怎么走、為什么不會(huì)丟節(jié)點(diǎn)”都能脫口而出。做到這一點(diǎn)之后你會(huì)發(fā)現(xiàn)不只是這道題整個(gè)鏈表分類的題目思路都通了不少。