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