力扣Hot 100第31題K個一組翻轉(zhuǎn)鏈表。這道題我前前后后刷了三遍每次以為自己懂了過兩個月再寫一次還是會在邊界條件上翻車。后來我才發(fā)現(xiàn)這道題根本不是在考你會不會翻轉(zhuǎn)鏈表而是在考你有沒有把鏈表操作里最要命的三個東西想清楚指針斷鏈、遞歸邊界、以及迭代時哨兵節(jié)點怎么用。如果你已經(jīng)在刷Hot 100大概率不是第一次碰鏈表反轉(zhuǎn)了。第206題反轉(zhuǎn)鏈表是入門第92題反轉(zhuǎn)鏈表II是進階到這一題就是綜合大考把鏈表按K個一組切段每段內(nèi)部反轉(zhuǎn)段與段之間還要接上最后不足K個的部分保持原樣。邏輯不復(fù)雜但寫出來到處都是坑。今天就把我在這道題上踩過的所有坑連同可以直接抄的完整代碼一起寫出來希望能幫你少走彎路。1. 題目拆解先搞懂“K個一組翻轉(zhuǎn)鏈表”到底在考什么1.1 題目原意與輸入輸出形態(tài)題目描述很簡潔給你一個鏈表每K個節(jié)點一組進行翻轉(zhuǎn)返回修改后的鏈表。K是一個正整數(shù)它的值小于或等于鏈表的長度。如果節(jié)點總數(shù)不是K的整數(shù)倍那么最后剩余的節(jié)點應(yīng)該保持原有順序。給你舉個例子。鏈表是1 - 2 - 3 - 4 - 5K等于2翻轉(zhuǎn)后應(yīng)該得到2 - 1 - 4 - 3 - 5。如果K等于3翻轉(zhuǎn)后應(yīng)該得到3 - 2 - 1 - 4 - 5。最后剩下的兩個節(jié)點4和5不足一組保持原順序不動。這道題的核心操作可以拆成三層第一層把整條鏈表切成多段每段正好K個節(jié)點。第二層對每一段內(nèi)部做完整的鏈表反轉(zhuǎn)。第三層把反轉(zhuǎn)后的每一段重新拼接起來并且處理好段與段之間的連接關(guān)系。很多朋友一上來就想著把所有節(jié)點一次性處理完結(jié)果繞進去出不來。其實正確的姿勢是先切段再反轉(zhuǎn)最后拼接三步分開想邏輯就清晰了。1.2 這道題為什么是Hot 100里的分水嶺Hot 100里鏈表題不少但這道題的位置非常特殊。它排在鏈表系列的中間偏后階段很多刷題人走到這里會明顯感到吃力。原因很簡單它同時考察了遞歸思想、指針操作、邊界處理和模塊化拆解能力。你可能會說反轉(zhuǎn)鏈表我也會遞歸我也會怎么合在一起就寫不出來了問題出在“組合”上。反轉(zhuǎn)鏈表只需要維護兩個指針但這里你還要維護“當前組的頭尾”“下一組的起點”“上一組拼接的位置”變量一多腦子就亂。而且這道題在面試里屬于高頻題。我印象里至少有三次模擬面試和真實面試遇到它面試官通常不會只滿足于你寫出一種解法他還會追問遞歸的空間復(fù)雜度是多少能不能改成迭代如果K等于1怎么辦鏈表長度剛好是K的倍數(shù)怎么辦這些追問才是拉開差距的地方。1.3 刷這道題之前你需要先掌握的基礎(chǔ)如果你之前沒怎么碰過鏈表我建議先花半小時把下面幾個基礎(chǔ)操作練熟不然直接上這題會很痛苦鏈表的遍歷用cur cur-next走完整個鏈表。單鏈表反轉(zhuǎn)用三指針prev/cur/next迭代反轉(zhuǎn)或者用遞歸反轉(zhuǎn)。哨兵節(jié)點在頭節(jié)點前面加一個虛擬節(jié)點用來統(tǒng)一處理頭節(jié)點變化的場景。遞歸的返回值語義想清楚每一層遞歸返回的到底是哪個節(jié)點。其中“返回值語義”是最容易懵的。很多人在寫遞歸鏈表題時根本不知道自己 return 出去的是什么只會照著模板套一旦題目變形就報廢。等下在實現(xiàn)部分我會專門展開講。2. 核心思路遞歸分組 局部反轉(zhuǎn)的設(shè)計邏輯2.1 為什么先考慮遞歸而不是純迭代我第一次做這道題時第一反應(yīng)是用迭代硬剛用一個外層循環(huán)遍歷鏈表每K個切一段反轉(zhuǎn)再接回去。結(jié)果寫出來一坨代碼變量命名都是p1 p2 p3跑起來一堆邊界錯誤調(diào)了半天心態(tài)爆炸。后來換了遞歸思路一下子清爽很多。遞歸想問題的模式是我只管當前這一組怎么處理剩下的交給函數(shù)自己。你不用在一層邏輯里同時操心“上一組怎么接”“下一組怎么找”“全部反轉(zhuǎn)完怎么收尾”只需要定義清楚一件事當前這K個節(jié)點怎么翻轉(zhuǎn)翻轉(zhuǎn)后返回什么然后讓函數(shù)對剩余鏈表重復(fù)同樣的操作。用遞歸還有個額外的好處代碼讀起來特別像題目的文字描述。“每K個一組翻轉(zhuǎn)鏈表”這句話翻譯成遞歸就是先反轉(zhuǎn)前K個然后對剩下的鏈表遞歸調(diào)用同一個函數(shù)再把兩部分接起來。這樣代碼和思路是一一對應(yīng)的面試講起來也順。2.2 三步走找長度、局部翻轉(zhuǎn)、遞歸銜接遞歸版的核心思路可以拆成三步第一步從當前節(jié)點出發(fā)向后走K步。如果走不滿K步說明剩下的節(jié)點不足一組直接返回當前頭節(jié)點保持原樣。第二步反轉(zhuǎn)從當前節(jié)點開始的K個節(jié)點。這一步本質(zhì)就是普通的單鏈表反轉(zhuǎn)只不過限制反轉(zhuǎn)長度為K。反轉(zhuǎn)之后原來的頭節(jié)點變成了這一組的尾節(jié)點原來的第K個節(jié)點變成了這一組的新頭。第三步把“這一組的尾節(jié)點”的 next 指針指向“剩余鏈表遞歸處理后的頭節(jié)點”。然后返回這一組的新頭節(jié)點。這里有個非常關(guān)鍵的地方反轉(zhuǎn)前你要先保存“第K1個節(jié)點”的位置因為反轉(zhuǎn)過程中會改變指針指向如果不提前保存反轉(zhuǎn)完就找不到后面的鏈表了。這個細節(jié)看似簡單卻是最容易翻車的點。2.3 邊界條件的處理邏輯這道題的邊界條件主要有四個我以前每個都踩過鏈表為空或者K小于等于1直接返回原鏈表。K等于1意味著每1個一組翻轉(zhuǎn)翻轉(zhuǎn)等于沒翻屬于無效操作。剩下的節(jié)點不足K個保持原順序直接返回。判斷方法就是走K步時提前遇到了NULL。鏈表長度剛好是K的倍數(shù)最后一組也要正常翻轉(zhuǎn)不能多翻也不能少翻。這種情況其實在“走K步剛好走到NULL”時已經(jīng)處理好了。只有一個節(jié)點的情況不管K是多少返回它自己。邊界問題最好的處理方式不是靠記憶去背而是在寫代碼前先畫幾個測試用例空鏈表、單節(jié)點、長度剛好等于K、長度是K的倍數(shù)加1、長度是K的倍數(shù)減1。把這幾個用例在紙上走一遍邊界條件基本就覆蓋全了。2.4 用頭插法理解“為什么局部反轉(zhuǎn)不會亂”很多人覺得局部反轉(zhuǎn)容易亂其實是沒理解頭插法的本質(zhì)。你可以把翻轉(zhuǎn)K個節(jié)點想象成做這樣一個動作把一串珠子里的前K顆倒個個兒然后再和后面的珠子接上。頭插法的過程是依次把當前節(jié)點摘下來插到這一組的最前面。第一個節(jié)點被插到最前面后變成最后一個第二個節(jié)點插到它前面第三個節(jié)點又插到更前面如此往復(fù)K輪之后原有的順序就被完全倒過來了。這個過程不涉及跳來跳去的復(fù)雜指針變換只要保證“每次摘下當前節(jié)點之前先把它的下一個節(jié)點用臨時變量存起來”就不會斷鏈。很多教科書把這個臨時變量叫next我習慣叫tmp意思都一樣它是你操作鏈表的保險繩。3. C語言遞歸版完整實現(xiàn)逐行拆解3.1 結(jié)構(gòu)體定義與輔助函數(shù)先復(fù)習一下單鏈表的標準結(jié)構(gòu)體定義struct ListNode { int val; struct ListNode *next; };這個結(jié)構(gòu)體在力扣里已經(jīng)給你定義好了本地練習時需要自己寫。我每次本地調(diào)試都會額外寫一個輔助函數(shù)用來創(chuàng)建鏈表和打印鏈表方便肉眼檢查結(jié)果。// 根據(jù)數(shù)組創(chuàng)建鏈表 struct ListNode* createList(int* arr, int n) { if (n 0) return NULL; struct ListNode* head malloc(sizeof(struct ListNode)); head-val arr[0]; head-next NULL; struct ListNode* cur head; for (int i 1; i n; i) { struct ListNode* node malloc(sizeof(struct ListNode)); node-val arr[i]; node-next NULL; cur-next node; cur node; } return head; } // 打印鏈表 void printList(struct ListNode* head) { struct ListNode* cur head; while (cur) { printf(%d - , cur-val); cur cur-next; } printf(NULL\n); }這兩個函數(shù)看起來簡單但我強烈建議你寫。調(diào)試鏈表題不比調(diào)試數(shù)組題沒有可視化輸出全靠腦袋模擬指針變化很容易算錯。有個打印函數(shù)每次跑完一眼就能看到結(jié)果對不對。3.2 局部反轉(zhuǎn)函數(shù)兩種寫法反轉(zhuǎn)K個節(jié)點我試過兩種寫法各有各的適用場景。寫法一用循環(huán)次數(shù)控制反轉(zhuǎn)長度。struct ListNode* reverseK(struct ListNode* head, int k) { struct ListNode* prev NULL; struct ListNode* cur head; while (k--) { struct ListNode* tmp cur-next; cur-next prev; prev cur; cur tmp; } return prev; }這種寫法用while (k--)控制循環(huán)K次循環(huán)結(jié)束后prev指向反轉(zhuǎn)后的新頭cur指向下一組的起點。前提是調(diào)用前已經(jīng)確保從head開始至少有K個節(jié)點。寫法二用結(jié)束位置控制反轉(zhuǎn)長度。struct ListNode* reverseBetween(struct ListNode* head, struct ListNode* end) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! end) { struct ListNode* tmp cur-next; cur-next prev; prev cur; cur tmp; } return prev; }這種寫法反轉(zhuǎn)[head, end)這個左閉右開區(qū)間也就是從head開始一直反轉(zhuǎn)到end之前的那個節(jié)點。它更適合迭代版實現(xiàn)因為迭代版中已經(jīng)明確知道下一組的起點。我個人在遞歸版里習慣用寫法一因為已經(jīng)知道了K值直接反轉(zhuǎn)K個最直觀。迭代版里則用寫法二避免反復(fù)數(shù)K個節(jié)點。3.3 reverseKGroup函數(shù)逐行拆解遞歸版的reverseKGroup函數(shù)是整個解法的核心我先把完整代碼放出來然后逐行拆解struct ListNode* reverseKGroup(struct ListNode* head, int k) { // 邊界條件空鏈表或 K 小于等于 1直接返回 if (head NULL || k 1) { return head; } // 第一步從 head 出發(fā)走 k 步找到第 k 個節(jié)點 struct ListNode* cur head; int count 0; while (cur ! NULL count k) { cur cur-next; count; } // 如果走不滿 k 步說明剩余節(jié)點不足一組保持原樣 if (count k) { return head; } // 第二步反轉(zhuǎn)前 k 個節(jié)點 // 注意此時 cur 已經(jīng)指向第 k1 個節(jié)點 struct ListNode* newHead reverseK(head, k); // 第三步遞歸處理剩余鏈表并把當前組的尾節(jié)點接上去 // 原來的 head 反轉(zhuǎn)后變成了這一組的尾節(jié)點 head-next reverseKGroup(cur, k); return newHead; }第一段邊界條件不多說。第二段走K步是關(guān)鍵循環(huán)結(jié)束后如果count k說明走到了NULL還沒湊夠K個直接返回當前頭。如果count k那么cur正好指向第K1個節(jié)點也就是下一組的起點。注意這里cur的位置非常重要它被用于遞歸調(diào)用所以必須在反轉(zhuǎn)之前就確定并保存好。第三段調(diào)用reverseK(head, k)返回反轉(zhuǎn)后的新頭newHead。此時原來的head節(jié)點已經(jīng)變成了這一組的尾節(jié)點。然后執(zhí)行head-next reverseKGroup(cur, k)把這一組的尾節(jié)點接到“剩余鏈表遞歸處理后的頭節(jié)點”上。最后返回newHead這個返回值就是整個鏈表反轉(zhuǎn)后的頭節(jié)點。這里要特別強調(diào)一下返回值語義reverseKGroup返回的永遠是“傳入鏈表的頭節(jié)點”但這個頭節(jié)點在每一層遞歸里可能已經(jīng)變了。第一層傳入的是原始head返回的是整條鏈表反轉(zhuǎn)后的頭節(jié)點第二層傳入的是第二組的頭節(jié)點返回的是第二組反轉(zhuǎn)后的頭節(jié)點。你只要記住這個函數(shù)接受一條鏈表返回這條鏈表按K個一組翻轉(zhuǎn)后的頭節(jié)點。3.4 復(fù)雜度分析與算法驗證時間復(fù)雜度是O(n)其中n是鏈表節(jié)點總數(shù)。每個節(jié)點最多被訪問兩次一次在走K步判斷長度時一次在反轉(zhuǎn)時。雖然看起來有兩輪遍歷但兩個循環(huán)加起來還是線性級別。空間復(fù)雜度是O(n/k)這是遞歸棧的深度。因為每處理完一組K個節(jié)點就遞歸調(diào)用一次調(diào)用次數(shù)等于組數(shù)n/k。如果K比較大棧深度會小一些如果K比較小比如K等于2棧深度就是n/2。我在本地用一個長度為7、K等于3的鏈表做了測試過程如下輸入1 - 2 - 3 - 4 - 5 - 6 - 7 第一層反轉(zhuǎn) 1 - 2 - 3得到 3 - 2 - 1cur 指向 4 然后對 4 - 5 - 6 - 7 遞歸 第二層反轉(zhuǎn) 4 - 5 - 6得到 6 - 5 - 4cur 指向 7 然后對 7 遞歸 第三層count 1 3不足一組直接返回 7 拼接6 - 5 - 4 的尾節(jié)點 4 接到 7 拼接3 - 2 - 1 的尾節(jié)點 1 接到 6 - 5 - 4 - 7 輸出3 - 2 - 1 - 6 - 5 - 4 - 7跑出來的結(jié)果和預(yù)期完全一致。這個例子覆蓋了兩種情況整組翻轉(zhuǎn)和末尾不足一組保持原樣回頭你驗證代碼時可以直接用。4. 迭代版改良用哨兵節(jié)點消滅遞歸?？臻g4.1 面試官為什么愛追問迭代寫法遞歸版雖然思路清晰但有一個天然缺陷空間復(fù)雜度是O(n/k)。如果鏈表很長、K又很小遞歸棧會占用不少內(nèi)存。更麻煩的是如果K剛好等于1遞歸深度就是n鏈表一長就容易爆棧。所以面試官經(jīng)常會追問一句能不能用迭代實現(xiàn)他不是真的覺得遞歸代碼有問題而是想考察你對“遞歸本質(zhì)是?！边@件事有沒有認知以及能不能用循環(huán)手動模擬這個過程。我個人的經(jīng)驗是面試時先把遞歸版講清楚然后主動提一句“這個解法空間復(fù)雜度是O(n/k)如果需要優(yōu)化成O(1)空間可以用迭代加哨兵節(jié)點實現(xiàn)”面試官通常會對這個加分項很滿意。4.2 哨兵節(jié)點的妙用迭代版的思路和遞歸版類似但多了一個非常重要的角色哨兵節(jié)點。為什么要用哨兵節(jié)點因為每翻轉(zhuǎn)一組頭節(jié)點都在變化。第一組翻轉(zhuǎn)后原來的頭變成了尾新頭變成了原來的第K個節(jié)點。如果沒有哨兵節(jié)點每次都要單獨判斷“當前是不是第一組”代碼會多出很多分支。加一個虛擬頭節(jié)點dummy讓dummy-next始終指向當前最新的頭節(jié)點問題就統(tǒng)一了。迭代版還需要維護幾個關(guān)鍵指針prevGroupEnd上一組的尾節(jié)點也是當前組拼接的位置。groupStart當前組的第一個節(jié)點也就是待反轉(zhuǎn)的起點。nextGroupStart當前組的第K1個節(jié)點也就是下一組的起點。整個流程是一個外層循環(huán)每次檢查剩余節(jié)點是否夠K個夠就反轉(zhuǎn)當前組把上一組接到新頭上把當前組的尾節(jié)點接到下一組然后更新指針進入下一輪。4.3 迭代版完整代碼struct ListNode* reverseKGroup(struct ListNode* head, int k) { if (head NULL || k 1) { return head; } struct ListNode dummy; // 哨兵節(jié)點不在堆上分配 dummy.next head; struct ListNode* prevGroupEnd dummy; while (1) { // 檢查剩余節(jié)點是否夠 k 個 struct ListNode* kth prevGroupEnd; for (int i 0; i k; i) { kth kth-next; if (kth NULL) { return dummy.next; // 不足 k 個直接返回 } } // 確定當前組的范圍 struct ListNode* groupStart prevGroupEnd-next; struct ListNode* nextGroupStart kth-next; // 反轉(zhuǎn)當前組的 k 個節(jié)點 struct ListNode* prev NULL; struct ListNode* cur groupStart; while (cur ! nextGroupStart) { struct ListNode* tmp cur-next; cur-next prev; prev cur; cur tmp; } // 拼接上一組尾節(jié)點接到新頭當前組尾節(jié)點接到下一組 prevGroupEnd-next prev; groupStart-next nextGroupStart; // 更新上一組尾節(jié)點為當前組的尾節(jié)點 prevGroupEnd groupStart; } }這段代碼有幾處容易出錯的地方需要提醒。第一個是找第K個節(jié)點的循環(huán)。這里kth初始指向prevGroupEnd然后循環(huán)K次每次往后走一步。注意第一次循環(huán)時kth-next就是groupStart所以循環(huán)結(jié)束后kth正好是當前組的第K個節(jié)點而不是第K1個。如果中途遇到NULL說明不夠K個直接返回dummy.next。第二個是反轉(zhuǎn)區(qū)間的控制。while (cur ! nextGroupStart)表示當前組的范圍是[groupStart, nextGroupStart)左閉右開。反轉(zhuǎn)結(jié)束后prev指向這一組的新頭groupStart變成尾節(jié)點cur等于nextGroupStart。第三個是拼接順序。prevGroupEnd-next prev先把上一組的尾接到新頭上groupStart-next nextGroupStart再把當前組的尾接到下一組起點。這兩個賦值順序不能反因為groupStart和nextGroupStart都用到了如果先改了groupStart-next后面再用groupStart還是一樣的所以誰先誰后其實不影響。真正重要的是拼接必須發(fā)生在反轉(zhuǎn)之后而不是之前。第四是更新prevGroupEnd groupStart。注意這里用的是groupStart而不是prev因為groupStart反轉(zhuǎn)后就是當前組的尾節(jié)點它是下一輪循環(huán)的拼接起點。很多人這里寫錯成prev導(dǎo)致鏈表斷裂。空間復(fù)雜度是O(1)只用了幾個臨時指針。時間復(fù)雜度依然是O(n)每個節(jié)點同樣最多訪問兩次。4.4 遞歸版和迭代版怎么選我把兩個版本放在一起對比過列一個表格方便你選擇對比項遞歸版迭代版思路清晰度高和題目描述直接對應(yīng)中需要理解多個指針維護代碼量較簡潔稍長空間復(fù)雜度O(n/k)O(1)邊界處理難度較容易較容易但有更多指針要維護面試溝通效率高容易講明白中需要畫圖輔助說明我的建議是筆試和刷題用遞歸版省時間、留著精力想其他題面試如果被問到優(yōu)化再默寫迭代版。兩個都寫熟才是這道題的正確打開方式。5. 常見錯誤與調(diào)試實錄5.1 錯誤一沒有保存next指針導(dǎo)致斷鏈這是我見過最多的錯誤也是新手最容易犯的。反轉(zhuǎn)鏈表時每走一步都要先把cur-next保存到臨時變量里因為一旦執(zhí)行cur-next prev原來的下一個節(jié)點就找不回來了。如果你在反轉(zhuǎn)過程中發(fā)現(xiàn)最后輸出只有第一個節(jié)點或者鏈表憑空少了一截十有八九是這里出了問題。正確做法是在cur-next prev之前先寫struct ListNode* tmp cur-next;然后用tmp往后推進。這句話值得寫成注釋貼在代碼最上面鏈表的任何指針修改先保存后繼。5.2 錯誤二反轉(zhuǎn)次數(shù)多算一次或少算一次還拿反轉(zhuǎn)K個節(jié)點舉例。如果你用while (k--)循環(huán)體執(zhí)行K次后cur指向第K1個節(jié)點。但如果你不小心寫成了while (--k)或者while (k 1)循環(huán)只執(zhí)行K-1次反轉(zhuǎn)結(jié)果就會少一個節(jié)點。我調(diào)試時碰到過一種很隱蔽的情況K等于3我寫while (--k)結(jié)果反轉(zhuǎn)完只剩兩個節(jié)點被翻轉(zhuǎn)第三個節(jié)點還掛在后面。從輸出看只是順序不對代碼檢查時卻不容易發(fā)現(xiàn)。排查方法很簡單在循環(huán)里打一個計數(shù)器看看到底執(zhí)行了幾次。5.3 錯誤三不足K個也反轉(zhuǎn)了遞歸版里如果走K步時遇到NULL應(yīng)該直接返回當前頭。但很多人寫完while (cur count k)之后忘了檢查count k的情況直接就去反轉(zhuǎn)了。結(jié)果就是最后一組不足K個的節(jié)點也被翻轉(zhuǎn)和題目要求不符。一個實用的自查技巧測試用例里一定要包含“鏈表長度不是K的整數(shù)倍”的case。比如長度為5、K為2或者長度為7、K為3跑一遍就能暴露這個問題。5.4 錯誤四遞歸返回的節(jié)點接錯遞歸版里有一行head-next reverseKGroup(cur, k)。這里的head是什么它是一組反轉(zhuǎn)前的頭節(jié)點反轉(zhuǎn)后變成這一組的尾節(jié)點。所以要把它的 next 指向剩余鏈表處理后的頭。如果這里你寫成了newHead-next或者寫成cur-next結(jié)果都會錯。newHead是整組的新頭它的 next 應(yīng)該指向這一組內(nèi)的下一個節(jié)點而不是剩余鏈表。很多人在這一步繞進去其實是沒想清楚反轉(zhuǎn)后這一組內(nèi)部的連接已經(jīng)由reverseK完成了head只需要負責組間連接。我建議在寫遞歸時養(yǎng)成一個習慣在注釋里寫清楚當前節(jié)點的角色變化。比如head // 反轉(zhuǎn)前是組內(nèi)第一個節(jié)點反轉(zhuǎn)后是組內(nèi)最后一個節(jié)點這樣就不會搞混。5.5 調(diào)試技巧寫一個打印函數(shù)比你干瞪眼強鏈表題的調(diào)試遠比數(shù)組題麻煩因為你看不到內(nèi)存里的指針指向。我強烈建議在本地環(huán)境里寫一個printList輔助函數(shù)每做一步關(guān)鍵操作就打印一次鏈表狀態(tài)。當年我調(diào)這道題時就是靠打印函數(shù)一步步看懂了指針變化才徹底理解了遞歸的執(zhí)行過程。力扣在線編輯器也支持打印printf也會輸出到控制臺只是平時不?？吹健Ｄ阃耆梢栽谡{(diào)試時臨時加幾行printf確認無誤后再刪掉。另外一個小技巧用數(shù)組輔助構(gòu)造測試鏈表。直接手寫head-next-next太累了用createList函數(shù)從數(shù)組初始化可以快速生成任意結(jié)構(gòu)的鏈表測試用例看得清清楚楚。6. 從這道題延伸出去的考點與刷題建議6.1 和它強相關(guān)的變體題這道題刷完有幾道題建議順手一起鞏固?？偨Y(jié)就是K個一組翻轉(zhuǎn)鏈表是鏈表反轉(zhuǎn)系列的集大成者學會它等于同時掌握了反轉(zhuǎn)鏈表I、II和兩兩交換節(jié)點的核心思路。反轉(zhuǎn)鏈表力扣206基礎(chǔ)版學會三指針迭代和遞歸兩種反轉(zhuǎn)寫法。反轉(zhuǎn)鏈表II力扣92指定區(qū)間反轉(zhuǎn)需要定位區(qū)間頭尾是K個一組翻轉(zhuǎn)的區(qū)間版。兩兩交換鏈表中的節(jié)點力扣24本質(zhì)上就是K等于2的“K個一組翻轉(zhuǎn)鏈表”做完這題再去做24會發(fā)現(xiàn)極其簡單。我刷題時習慣把同類型題放在一起集中做比如一周內(nèi)專門刷鏈表反轉(zhuǎn)類。這樣知識點會形成網(wǎng)絡(luò)而不是零散的知識點。單獨刷一道題過兩周就忘了連著刷一類題才會真正形成肌肉記憶。6.2 面試現(xiàn)場怎么講這道題如果你在面試中遇到這道題不要上來就寫代碼先給面試官畫圖。畫鏈表是數(shù)據(jù)結(jié)構(gòu)題的基本素養(yǎng)尤其是涉及指針變換的題畫圖能幫你理清思路也能讓面試官看到你的結(jié)構(gòu)化思考。講題思路可以按這個順序來先講遞歸版從當前頭出發(fā)走K步不足K個直接返回否則反轉(zhuǎn)前K個遞歸處理剩余鏈表然后把兩部分接起來。再主動補充迭代版提到遞歸的空間復(fù)雜度是O(n/k)如果希望O(1)空間可以用哨兵節(jié)點加循環(huán)實現(xiàn)。最后講邊界條件空鏈表、K等于1、長度不足K、長度剛好是K的倍數(shù)。面試官通常會順著你的思路追問一兩個細節(jié)比如“迭代版中prevGroupEnd為什么用原來的groupStart更新”“dummy節(jié)點行不行用棧上分配還是堆上分配”。這兩個問題我建議自己先想明白回答起來會更從容。6.3 刷題方式上的一點個人建議Hot 100不是刷一遍就完事的。我的個人經(jīng)驗是三輪刷法第一輪按標簽刷快速過思路第二輪隨機打亂檢驗記憶第三輪只刷錯題和不會的題。這道K個一組翻轉(zhuǎn)鏈表我第一輪刷的時候磕磕絆絆第二輪已經(jīng)能順暢寫遞歸版第三輪基本可以默寫出兩個版本。錯題本也很重要。我會給每一道錯題記錄三行題型分類、卡住的原因、下次要特別注意的點。對于這道題我記的是“指針操作題注意保存next、注意返回值語義”。過了一個月回來看一眼就能回憶起關(guān)鍵坑點。刷題這件事最難的不是代碼而是和遺忘作斗爭。你不需要一天刷很多題但你需要定期復(fù)習尤其是那些讓你糾結(jié)良久的題。它們才是真正提升你算法水平的部分。每當你覺得自己“又忘了怎么寫”說明這個知識點正在真正被你吸收。這道題我到現(xiàn)在都還會偶爾翻出來重新寫一遍每次寫都有一些新感悟。鏈表操作的樂趣就在這里指針還是那兩根指針但在不同的排列組合下能變出無數(shù)種題目。希望你看完這篇能把這道Hot 100里的硬骨頭啃下來以后遇到任何鏈表反轉(zhuǎn)題都能胸有成竹。