北京
我今天遇到了一道看似簡單、實(shí)則容易讓遞歸陷入死循環(huán)的鏈表題。題目是LeetCode第25題“K個(gè)一組翻轉(zhuǎn)鏈表”，要求每k個(gè)節(jié)點(diǎn)為一組進(jìn)行翻轉(zhuǎn)，如果最后剩下的節(jié)點(diǎn)不夠k個(gè)，就保持原樣。這個(gè)規(guī)則本身很清晰，但我的第一次嘗試卻在最簡單的用例上翻了車。
第一次提交時(shí)，我直接上手寫了一個(gè)翻轉(zhuǎn)前k個(gè)節(jié)點(diǎn)的邏輯，然后遞歸處理剩余部分。測試用例是head=[1,2,3,4,5],k=2，預(yù)期輸出應(yīng)該是[2,1,4,3,5]。我原本以為這段代碼會(huì)干凈利落地跑完，結(jié)果系統(tǒng)報(bào)錯(cuò)“時(shí)間超限”。問題出在哪兒？后來復(fù)盤才發(fā)現(xiàn)，我在遞歸調(diào)用前并沒有檢查剩下的節(jié)點(diǎn)是否夠k個(gè)。這意味著，當(dāng)鏈表尾部的節(jié)點(diǎn)數(shù)不足k時(shí)，我的遞歸仍然試圖翻轉(zhuǎn)它們，導(dǎo)致無限循環(huán)或重復(fù)處理。
第二次嘗試我補(bǔ)上了這個(gè)漏洞。在進(jìn)入翻轉(zhuǎn)邏輯之前，先用一個(gè)循環(huán)向前探測k步，確認(rèn)節(jié)點(diǎn)數(shù)量足夠。如果不夠，直接返回當(dāng)前頭節(jié)點(diǎn)，不再遞歸。這個(gè)改動(dòng)讓代碼表現(xiàn)完全不同——同樣的測試用例，運(yùn)行時(shí)間從超限跳到了0毫秒。整個(gè)思路變成了兩步走：第一步，數(shù)節(jié)點(diǎn)、判斷是否有k個(gè)；第二步，翻轉(zhuǎn)這k個(gè)節(jié)點(diǎn)，然后遞歸連接后續(xù)。這種“先驗(yàn)證、再操作”的節(jié)奏，在鏈表遞歸里尤其重要。
我順帶看了社區(qū)里其他解法，有一種寫法被很多人采用，思路是先遍歷整個(gè)鏈表拿到總長度size，算出需要翻轉(zhuǎn)的組數(shù)size//k，然后在一個(gè)循環(huán)里逐組翻轉(zhuǎn)。這種做法的好處是徹底避免了遞歸深度失控的問題，尤其適合鏈表長度遠(yuǎn)大于k的場景。代碼中會(huì)維護(hù)一個(gè)啞節(jié)點(diǎn)dummy，用它作為每一組翻轉(zhuǎn)的“前驅(qū)”，翻轉(zhuǎn)完一組后移動(dòng)指針，繼續(xù)下一組，整個(gè)過程是迭代式的，邏輯非常扁平化。
今天這道題給我的最大感受是：遞歸雖然優(yōu)雅，但在邊界條件上極其脆弱。一個(gè)漏掉的count
特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺(tái)“網(wǎng)易號(hào)”用戶上傳并發(fā)布，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
