1. 第一反應(yīng)與標(biāo)準(zhǔn)答案之間隔著一個(gè)排序算法選型先把這道題擺出來(lái)力扣hot100第33題排序鏈表。題面非常簡(jiǎn)潔——給你一個(gè)鏈表的頭節(jié)點(diǎn)要求按升序把它排好進(jìn)階條件有兩個(gè)時(shí)間復(fù)雜度O(n log n)空間復(fù)雜度O(1)。字符串很短但殺傷力很大因?yàn)樗瑫r(shí)考三件事鏈表操作基本功、排序算法的本質(zhì)理解、以及空間復(fù)雜度的嚴(yán)格把控。我第一次做這道題的時(shí)候第一反應(yīng)其實(shí)很野把鏈表遍歷一遍把所有節(jié)點(diǎn)值存進(jìn)數(shù)組對(duì)數(shù)組排序再按順序串回鏈表。這個(gè)思路在思路上完全沒(méi)問(wèn)題但是直接違反進(jìn)階條件——空間復(fù)雜度O(n)不說(shuō)還繞開(kāi)了鏈表操作的核心考察點(diǎn)。面試官看到這種解法基本等于你在告訴他“我不太會(huì)處理鏈表指針”。話說(shuō)回來(lái)為什么這道題能進(jìn)hot100而且常年穩(wěn)定在熱門題單的前列因?yàn)樗鼛缀醢选版湵眍}的通用難點(diǎn)”全部濃縮在了一個(gè)問(wèn)題里找中點(diǎn)、斷開(kāi)鏈表、合并有序鏈表、處理邊界條件。而且更重要的是它逼著你做一次排序算法的選型判斷而不是無(wú)腦調(diào)用sort函數(shù)。數(shù)組排序我們可以依賴語(yǔ)言內(nèi)置的排序函數(shù)但鏈表不行——鏈表的隨機(jī)訪問(wèn)是O(n)很多在數(shù)組上優(yōu)雅的算法直接套到鏈表上會(huì)變得笨拙甚至無(wú)法落地。那我們先把候選算法過(guò)一遍看看誰(shuí)的復(fù)雜度匹配題目要求誰(shuí)又是看似可行實(shí)則踩坑。算法時(shí)間復(fù)雜度空間復(fù)雜度鏈表上的可行性冒泡/插入/選擇O(n^2)O(1)可行但超時(shí)n開(kāi)到10^5直接等死快速排序平均O(n log n)O(log n)~O(n)需要隨機(jī)訪問(wèn)priovt鏈表實(shí)現(xiàn)麻煩且不穩(wěn)定堆排序O(n log n)O(n)建堆額外空間不符合O(1)要求歸并排序遞歸O(n log n)O(log n)遞歸棧最容易想到但遞歸棧不算O(1)歸并排序迭代/自底向上O(n log n)O(1)完全符合進(jìn)階要求這就是正解看到這個(gè)表格答案已經(jīng)很明顯了歸并排序。但歸并排序也有兩個(gè)版本——自頂向下和自底向上。很多教程只講自頂向下遞歸版本因?yàn)榇a短、邏輯清晰看起來(lái)就很好背。但問(wèn)題是面試官如果追問(wèn)一句“你覺(jué)得空間復(fù)雜度達(dá)標(biāo)嗎”你就得拿“遞歸棧也算空間”這層窗戶紙來(lái)說(shuō)明情況。想知道這層窗戶紙后面藏著什么我們先從最直觀的遞歸版本開(kāi)始拆解。2. 自頂向下歸并排序最直觀的解法但未必是終版2.1 歸并排序到底在鏈路上做了什么事數(shù)組上的歸并排序核心是“先分后合”把數(shù)組一分為二各自排序再把兩個(gè)有序數(shù)組合并成一個(gè)。鏈表上做同樣的事情難點(diǎn)不在合并而在“分”。數(shù)組可以靠下標(biāo)O(1)找到中點(diǎn)鏈表不行鏈表找中點(diǎn)只能靠快慢指針快指針每次走兩步慢指針每次走一步快指針到終點(diǎn)時(shí)慢指針正好落在中間。這是一個(gè)非常經(jīng)典的前置技巧你會(huì)在很多鏈表題里反復(fù)見(jiàn)到它比如判斷鏈表是否有環(huán)、尋找鏈表中間節(jié)點(diǎn)、以及這道題里用來(lái)切分鏈表。找到中點(diǎn)之后要做一件非常關(guān)鍵的事把鏈表從中間斷成兩條獨(dú)立的鏈表。這里有個(gè)細(xì)節(jié)特別容易出錯(cuò)——找到中點(diǎn)后要把中點(diǎn)的前一個(gè)節(jié)點(diǎn)的next置為空否則你遞歸處理左半部分時(shí)右半部分的節(jié)點(diǎn)還是能通過(guò)next指針被訪問(wèn)到整個(gè)遞歸結(jié)構(gòu)就亂了。實(shí)際操作中有兩種做法第一種是先找到slow和fast然后用一個(gè)prev指針記錄slow的前驅(qū)最后prev.next None第二種是fast先走兩步、slow走一步這種雙指針節(jié)奏讓slow最終落在左半部分的最后一個(gè)節(jié)點(diǎn)上然后直接cur.next None。我用的是第二種思路找一個(gè)“左閉右開(kāi)”的切分方式代碼更干凈。具體可以這樣寫def get_mid(head): if not head: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next return slow2.2 遞歸歸并版本的完整代碼日常刷題或面試時(shí)如果時(shí)間緊迫先寫遞歸版本是完全可以的因?yàn)樗壿嬜钪庇^、不容易出bug。合并兩個(gè)有序鏈表的部分大家應(yīng)該很熟了——用一個(gè)dummy節(jié)點(diǎn)作為結(jié)果鏈表的頭然后雙指針依次歸并。完整代碼長(zhǎng)這樣class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def sortList(head): if not head or not head.next: return head mid get_mid(head) right_head mid.next mid.next None left sortList(head) right sortList(right_head) return merge(left, right) def merge(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next if l1: cur.next l1 if l2: cur.next l2 return dummy.next這個(gè)代碼的優(yōu)點(diǎn)是結(jié)構(gòu)極其清晰遞歸邊界、分治邏輯、合并邏輯各司其職。面試時(shí)先寫這個(gè)版本至少你能保證提交通過(guò)、邏輯無(wú)誤。但注意我前面表格里寫的那一行——遞歸版本的空間復(fù)雜度是O(log n)來(lái)自遞歸調(diào)用棧的深度。對(duì)于一個(gè)完全平衡的切分遞歸樹(shù)深度是log n但如果你的找中點(diǎn)函數(shù)寫歪了鏈表切分不均勻遞歸深度可能惡化甚至接近O(n)那就徹底翻車。2.3 遞歸版本真正的問(wèn)題不在性能而在“追問(wèn)”我見(jiàn)過(guò)很多刷題的人把遞歸版本背得滾瓜爛熟但面試官一句“你能讓空間復(fù)雜度嚴(yán)格變成O(1)嗎”就直接卡住。這里有一個(gè)關(guān)鍵認(rèn)知嚴(yán)格意義上的O(1)空間指的是除輸入輸出所占空間外輔助空間的消耗是常數(shù)級(jí)別不隨數(shù)據(jù)規(guī)模增長(zhǎng)。遞歸棧確實(shí)是輔助空間深度是log n所以不能算O(1)。這就把正解推向了一個(gè)方向——自底向上的迭代歸并排序。另外遞歸版本在極端輸入下還有爆棧風(fēng)險(xiǎn)。Python默認(rèn)遞歸深度大約1000層而鏈表的長(zhǎng)度上限是10^5雖然完全平衡切分下log2(10^5)約等于17層理論上是安全的但如果你的切分邏輯不均衡遞歸深度可能遠(yuǎn)超理論值。我有一次就因?yàn)間et_mid寫成了slowhead, fasthead的節(jié)奏導(dǎo)致切出來(lái)的左右鏈表長(zhǎng)度不均遞歸深度飆升最終在10^5級(jí)數(shù)據(jù)上直接RecursionError。這個(gè)坑后面我會(huì)詳細(xì)說(shuō)。所以結(jié)論是遞歸版本適合寫出來(lái)證明思路但如果你要“穩(wěn)穩(wěn)拿到進(jìn)階要求的滿分”必須掌握自底向上的迭代寫法。這也是本文真正的主角。3. 自底向上歸并排序真正滿足O(1)空間的寫法3.1 核心思路用子鏈表長(zhǎng)度控制合并輪次自底向上的歸并排序通俗地理解就是先把每個(gè)長(zhǎng)度為1的子鏈表看成已經(jīng)有序的兩兩合并成長(zhǎng)度為2的有序鏈表再把長(zhǎng)度為2的有序鏈表兩兩合并成長(zhǎng)度為4的有序鏈表以此類推直到整個(gè)鏈表有序。整個(gè)過(guò)程不遞歸、不切分全靠一個(gè)外層循環(huán)控制“步長(zhǎng)”subLength以及一堆指針在鏈表中穿針引線。這個(gè)思路聽(tīng)起來(lái)很簡(jiǎn)單但實(shí)現(xiàn)起來(lái)比遞歸版復(fù)雜得多主要在于鏈表不像數(shù)組那樣能通過(guò)下標(biāo)自由跳轉(zhuǎn)每一輪合并時(shí)你得手動(dòng)找到每一段的頭節(jié)點(diǎn)、手動(dòng)記錄上一段的尾部還得小心處理鏈表斷開(kāi)和連接。我用生活化的方式類比一下想象你有一排小卡片每張卡片寫著一個(gè)數(shù)字。第一輪你把相鄰兩張卡片按大小合并成一小摞有序卡片第二輪把相鄰兩小摞合并成一大摞每一輪結(jié)束后所有小摞內(nèi)部都是有序的。重復(fù)這個(gè)“合并相鄰兩摞”的動(dòng)作直到只剩一整摞整個(gè)隊(duì)列就有序了。上面這個(gè)過(guò)程的“小摞長(zhǎng)度”就是代碼里的subLength。它從1開(kāi)始每輪翻倍直到大于等于鏈表長(zhǎng)度排序結(jié)束。3.2 迭代歸并的完整代碼與逐行解析def sortList(head): if not head or not head.next: return head # 第一步獲取鏈表總長(zhǎng)度 length 0 cur head while cur: length 1 cur cur.next dummy ListNode(0) dummy.next head sub_length 1 while sub_length length: prev dummy cur dummy.next while cur: # 截取第一個(gè)長(zhǎng)度為sub_length的子鏈表 head1 cur for _ in range(sub_length - 1): if cur.next: cur cur.next else: break head2 cur.next cur.next None # 斷開(kāi)第一個(gè)子鏈表 cur head2 # 截取第二個(gè)長(zhǎng)度為sub_length的子鏈表 for _ in range(sub_length - 1): if cur and cur.next: cur cur.next else: break if cur: next_start cur.next cur.next None # 斷開(kāi)第二個(gè)子鏈表 cur next_start else: next_start None # 合并兩個(gè)子鏈表 merged merge(head1, head2) prev.next merged while prev.next: prev prev.next cur next_start sub_length 1 return dummy.next這段代碼看著長(zhǎng)但拆開(kāi)其實(shí)就四個(gè)動(dòng)作找第一段、找第二段、斷開(kāi)、合并、掛接。我逐個(gè)解釋。第一獲取鏈表總長(zhǎng)度。為什么需要length因?yàn)樽缘紫蛏系臍w并是“倍增輪次”的你總得知道什么時(shí)候該停。雖然也可以用“如果subLength大于等于鏈表長(zhǎng)度就?！眮?lái)判斷但沒(méi)有l(wèi)ength就無(wú)法判斷是否已經(jīng)合并完成。這個(gè)length每輪while循環(huán)的條件判斷都要用所以必須先遍歷一遍鏈表拿下它。第二dummy節(jié)點(diǎn)的意義。整個(gè)排序過(guò)程中鏈表的頭節(jié)點(diǎn)可能會(huì)因?yàn)楹喜⒍淖儭１热缭兼湵淼念^節(jié)點(diǎn)如果在第一輪合并中被放到了后面你要返回的新頭變成另一個(gè)節(jié)點(diǎn)。dummy節(jié)點(diǎn)保證無(wú)論頭節(jié)點(diǎn)怎么換dummy.next始終指向當(dāng)前有序鏈表的頭。這串邏輯和你在普通合并兩個(gè)有序鏈表時(shí)用dummy的思路完全一樣只不過(guò)這里的dummy貫穿了整個(gè)排序過(guò)程。第三也是最容易寫錯(cuò)的地方就是“找到兩個(gè)待合并鏈表并斷開(kāi)”。注意我的處理順序先讓cur從當(dāng)前段頭出發(fā)移動(dòng)subLength-1步找到第一段的尾節(jié)點(diǎn)此時(shí)cur.next指向第二段的頭先把它記為head2再把cur.next置空斷開(kāi)第一段然后把cur挪到head2的位置繼續(xù)移動(dòng)subLength-1步找第二段的尾節(jié)點(diǎn)把尾節(jié)點(diǎn)的next置為None同時(shí)記錄下一輪的起始節(jié)點(diǎn)next_start。我為什么反復(fù)強(qiáng)調(diào)“斷開(kāi)”因?yàn)閙erge函數(shù)合并兩條鏈表時(shí)循環(huán)條件通常是while l1 and l2。如果不把兩條鏈表的尾部封口即最后一個(gè)節(jié)點(diǎn)的nextNonemerge函數(shù)在合并完第一段和第二段后可能順著next指針把后面的節(jié)點(diǎn)也一并帶上導(dǎo)致排序結(jié)果完全錯(cuò)亂甚至出現(xiàn)環(huán)形引用、死循環(huán)。第四prev指針的維護(hù)。每合并完一對(duì)子鏈表要把合并結(jié)果掛到prev.next上然后讓prev沿著合并后的節(jié)點(diǎn)走到這段的尾部——因?yàn)橄乱粚?duì)子鏈表的合并結(jié)果要接在這個(gè)尾部后面。這里有另一種寫法是維護(hù)一個(gè)tail指針始終指向已排序部分的末尾效果一樣但用prev有一點(diǎn)好處它就是上一段的尾部天然適合作為下一個(gè)合并結(jié)果的掛載點(diǎn)。第五注意sub_length 1。左移一位就是乘2表示下一輪合并的步長(zhǎng)翻倍。很多教程寫subLength * 2效果完全一樣但位運(yùn)算在刷題黨里更常見(jiàn)性能上也沒(méi)差別看你個(gè)人習(xí)慣。3.3 merge函數(shù)里的小優(yōu)化頭插 vs 輔助節(jié)點(diǎn)迭代歸并中用到的merge函數(shù)和前面遞歸版本中的merge函數(shù)可以完全一樣都是dummy節(jié)點(diǎn)雙指針合并。但這里有一個(gè)性能優(yōu)化空間值得聊一聊。在合并兩條有序鏈表時(shí)常規(guī)寫法是def merge(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next if l1: cur.next l1 if l2: cur.next l2 return dummy.next這個(gè)寫法是通用且穩(wěn)妥的。但你在每一輪合并后要重新移動(dòng)prev到新鏈表的尾部這本身是O(sub_length)的。整個(gè)排序的輪數(shù)是log n輪每輪所有prev移動(dòng)加起來(lái)是O(n)所以總體仍然是O(n log n)。這個(gè)常數(shù)開(kāi)銷是可以接受的不必過(guò)度優(yōu)化。如果你非要追求極致性能可以做一個(gè)“尾插優(yōu)化”——在merge過(guò)程中不返回頭節(jié)點(diǎn)而是同時(shí)返回新的尾節(jié)點(diǎn)讓prev直接指向這個(gè)尾節(jié)點(diǎn)省去一輪遍歷。我試過(guò)這種寫法代碼會(huì)變長(zhǎng)而且容易在邊界條件上出錯(cuò)對(duì)面試和比賽來(lái)說(shuō)性價(jià)比不高。除非你的代碼在最后幾個(gè)測(cè)試用例上確實(shí)卡在了常數(shù)級(jí)超時(shí)否則——不推薦。4. 我寫這道題踩過(guò)的坑以及驗(yàn)證正確性的方法4.1 找中點(diǎn)卻忘了斷鏈排序變“串燒”這是我第一次實(shí)現(xiàn)遞歸歸并時(shí)犯的錯(cuò)。我用快慢指針找到了mid然后直接sortList(head)和sortList(mid.next)完全沒(méi)有把mid.next置空。結(jié)果是什么假設(shè)鏈表是4-2-1-3找中點(diǎn)找到節(jié)點(diǎn)2然后遞歸處理左半邊4-2和右半邊1-3。問(wèn)題是左半邊調(diào)用sortList(head)時(shí)head鏈表中節(jié)點(diǎn)2的next仍然指向節(jié)點(diǎn)1于是這個(gè)“左半邊”實(shí)際上包含了所有剩余節(jié)點(diǎn)。遞歸下去你會(huì)發(fā)現(xiàn)左右子問(wèn)題根本不是分的而是穿在一起互相糾纏最終要么無(wú)限遞歸要么合并出的結(jié)果完全亂套。排查這道問(wèn)題花了很久最后我用一個(gè)非常小的用例打印鏈表內(nèi)容的方式發(fā)現(xiàn)斷鏈這個(gè)動(dòng)作比“找中點(diǎn)”重要得多。自頂向下歸并排序中“分”的關(guān)鍵不是找到中點(diǎn)而是真正把鏈表分成互不可達(dá)的兩條獨(dú)立鏈。4.2 快慢指針節(jié)奏slow和fast的起點(diǎn)關(guān)系影響中點(diǎn)歸屬快慢指針找中點(diǎn)的代碼有很多變體最典型的兩個(gè)是slow, fast head, headfast走兩步、slow走一步fast到末尾時(shí)slow剛好在中點(diǎn)偏右的位置偶數(shù)長(zhǎng)度時(shí)。slow, fast head, head.nextfast先走一步slow略慢slow在中點(diǎn)偏左的位置即第一段最后一個(gè)節(jié)點(diǎn)。這兩個(gè)起點(diǎn)選擇會(huì)導(dǎo)致“中點(diǎn)落在哪一側(cè)”產(chǎn)生差異。如果你用第二種就天然拿到了左半部分的最后一個(gè)節(jié)點(diǎn)直接把slow.next置空就能完成斷鏈不需要額外的prev指針。我推薦這種寫法因?yàn)樗尅皵嚅_(kāi)左半邊和右半邊”這個(gè)動(dòng)作變得不費(fèi)腦。但要注意的是如果你用slow, fast head, head在偶數(shù)長(zhǎng)度的鏈表上slow會(huì)落在兩個(gè)“中間節(jié)點(diǎn)”中更靠右的那個(gè)此時(shí)你拿到的是右半部分的頭節(jié)點(diǎn)要斷鏈反而需要額外記錄前驅(qū)。這就比較繞了。4.3 迭代歸并中的經(jīng)典大坑合并完成后沒(méi)有把末尾置空這個(gè)坑幾乎人人都會(huì)踩一次。迭代歸并在每一輪結(jié)束時(shí)整個(gè)鏈表是“一段一段拼接起來(lái)”的。如果你在合并某兩段之后沒(méi)有對(duì)最后一段的next做封口處理那么當(dāng)subLength翻倍后下一輪從頭遍歷時(shí)會(huì)把上一輪合并后的殘鏈當(dāng)成一段完整的鏈表處理輕則排序錯(cuò)亂重則無(wú)限循環(huán)。具體來(lái)說(shuō)在每一輪內(nèi)部當(dāng)我找到head2后斷開(kāi)第一段時(shí)cur.next None這一步能保證第一段被切斷但第二段的尾部是在后續(xù)的cur.next None中斷開(kāi)的。有一個(gè)隱蔽的錯(cuò)誤是當(dāng)?shù)诙啽闅v時(shí)如果當(dāng)前所有剩余節(jié)點(diǎn)不足subLength那么最后一個(gè)子鏈表可能沒(méi)有足夠的節(jié)點(diǎn)來(lái)“兩兩配對(duì)”這時(shí)候我直接就把它掛在prev后面了——這樣做其實(shí)是正確的因?yàn)樽詈笠恍《渭词共慌鋵?duì)保持原樣即可反正上一輪已經(jīng)保證它內(nèi)部有序。但如果你在代碼里忘記在break后維護(hù)好cur指針的移動(dòng)軌跡這個(gè)“不足一段”的尾巴很容易被錯(cuò)誤地再次截?cái)鄬?dǎo)致節(jié)點(diǎn)丟失。4.4 邊界條件自查清單寫鏈表題邊界條件永遠(yuǎn)是bug的溫床。我總結(jié)了一份自檢清單每次寫完排序鏈表都逐項(xiàng)過(guò)一遍輸入情況預(yù)期行為容易漏掉的處理head為空返回None開(kāi)頭必須判斷if not head鏈表只有一個(gè)節(jié)點(diǎn)原樣返回if not head.next兩個(gè)節(jié)點(diǎn)正確交換找中點(diǎn)即左半段最后一個(gè)節(jié)點(diǎn)本身全部相同值順序不變排序結(jié)果穩(wěn)定合并時(shí)仍然能通過(guò)但不能出現(xiàn)死循環(huán)最大長(zhǎng)度10^5不超時(shí)、不爆內(nèi)存迭代歸并比遞歸穩(wěn)4.5 怎么驗(yàn)證自己寫對(duì)了刷題網(wǎng)站會(huì)直接幫你跑測(cè)試用例但很多人在本地調(diào)試時(shí)不會(huì)自己構(gòu)造鏈表。我提供一個(gè)簡(jiǎn)單的方法寫一個(gè)鏈表轉(zhuǎn)列表、列表轉(zhuǎn)鏈表的輔助函數(shù)然后隨機(jī)生成大量數(shù)組排序后和Python內(nèi)置sort的結(jié)果對(duì)比。import random def list_to_linked(arr): dummy ListNode(0) cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next def linked_to_list(head): res [] while head: res.append(head.val) head head.next return res for _ in range(1000): arr [random.randint(0, 100) for _ in range(random.randint(0, 50))] head list_to_linked(arr) sorted_head sortList(head) assert linked_to_list(sorted_head) sorted(arr), arr print(all passed)這個(gè)辦法對(duì)初學(xué)者來(lái)說(shuō)特別友好能在十秒內(nèi)發(fā)現(xiàn)各種邊界bug。比如剛才提到的斷鏈、丟節(jié)點(diǎn)、排序結(jié)果不穩(wěn)定等問(wèn)題用隨機(jī)數(shù)據(jù)撞幾次基本都會(huì)現(xiàn)出原形。我在本地寫迭代歸并版本的頭兩天全靠這個(gè)腳本幫我抓到三個(gè)隱蔽的bug。5. 從刷題到面試排序鏈表的變體與擴(kuò)展思路5.1 一道題串起一整套鏈表技能很多人刷題是孤立地刷做完一道忘一道但排序鏈表這道題非常適合當(dāng)“母題”來(lái)串知識(shí)點(diǎn)。它包含了鏈表操作中的四大基本功遍歷計(jì)數(shù)求鏈表長(zhǎng)度這個(gè)動(dòng)作簡(jiǎn)單但高頻快慢指針找中間節(jié)點(diǎn)幾乎所有“斷鏈”類題目的地基虛擬頭節(jié)點(diǎn)合并有序鏈表時(shí)讓頭節(jié)點(diǎn)處理變得統(tǒng)一指針斷開(kāi)與重連自底向上的迭代歸并中反復(fù)操作的核心能力。如果你把這道題徹底吃透再去做合并兩個(gè)有序鏈表、合并K個(gè)升序鏈表、兩兩交換鏈表中的節(jié)點(diǎn)、Reorder List這些題會(huì)感覺(jué)阻力小很多。它們本質(zhì)上用的都是同一套指針操作語(yǔ)言。5.2 變體一對(duì)K個(gè)有序鏈表做歸并排序鏈表這道題做完很自然會(huì)延伸出一個(gè)問(wèn)題如果我有K個(gè)有序鏈表怎么合并它們高效辦法是借助優(yōu)先級(jí)隊(duì)列(最小堆)時(shí)間復(fù)雜度是O(N log K)空間復(fù)雜度O(K)。這題的思路仍然和歸并排序一脈相承——你先把K個(gè)鏈表的頭節(jié)點(diǎn)丟進(jìn)堆里每次彈出最小的然后把它的next補(bǔ)進(jìn)堆循環(huán)直到堆空。另一種不用堆的做法就是兩兩合并先合并前兩個(gè)得到新鏈表再和第三個(gè)合并……時(shí)間復(fù)雜度是O(NK)性能差得多。所以如果面試官讓你寫合并K個(gè)有序鏈表優(yōu)先答優(yōu)先級(jí)隊(duì)列方案然后再提醒他“如果要求O(1)空間我們可以用自底向上的歸并改造”——這個(gè)應(yīng)答思路就能直接把排序鏈表里的經(jīng)驗(yàn)遷移過(guò)來(lái)。5.3 變體二鏈表上的其他排序場(chǎng)景排序鏈表屬于“不能隨機(jī)訪問(wèn)”的場(chǎng)景常見(jiàn)的替代方案是歸并。但還有一些鏈表排序題是特殊情況比如對(duì)含有重復(fù)值的鏈表進(jìn)行快速排序這時(shí)候遞歸版本其實(shí)也能實(shí)現(xiàn)只是partition變成了值比較鏈表切分代碼會(huì)非常繁瑣。實(shí)際面試中我很少見(jiàn)到有人用快速排序解鏈表題因?yàn)殒湵砜炫诺臅r(shí)間復(fù)雜度并不總是O(n log n)最壞情況會(huì)退化到O(n^2)。歸并排序是鏈表排序的天然最優(yōu)選擇原因無(wú)他——鏈表的“順序訪問(wèn)斷鏈拼接”特性正好匹配歸并排序的“合并有序序列”操作。5.4 迭代歸并對(duì)遞歸歸并何時(shí)勝出遞歸歸并的優(yōu)勢(shì)是代碼短、可讀性強(qiáng)、不容易有邏輯漏洞劣勢(shì)是遞歸?？臻g不計(jì)入O(1)以及極端情況下有爆棧風(fēng)險(xiǎn)。迭代歸并的優(yōu)勢(shì)是嚴(yán)格O(1)空間性能穩(wěn)定還能順帶展示你對(duì)遞歸棧底層的理解劣勢(shì)是代碼長(zhǎng)指針變量多邊界容易寫錯(cuò)。我的建議是面試中先寫出遞歸版本明確說(shuō)明它空間是O(log n)然后主動(dòng)提出“我可以改成自底向上的迭代版本實(shí)現(xiàn)O(1)空間”再把迭代代碼寫出來(lái)。這一套組合拳打下來(lái)既展示了思維的全面性也向面試官證明你對(duì)復(fù)雜度的理解不是背模板的而是真正掌握了底層邏輯。5.5 一些實(shí)戰(zhàn)心得這道題我寫了很多遍最后總結(jié)出幾個(gè)屢試不爽的經(jīng)驗(yàn)分享給正在刷題的朋友第一dummy節(jié)點(diǎn)在你的排序過(guò)程中永遠(yuǎn)不要?jiǎng)铀旧碇徊僮鱠ummy.next。一旦你忘了這一步后面所有指針都會(huì)亂套。把dummy當(dāng)成一個(gè)固定的“哨兵”你的思維負(fù)擔(dān)會(huì)小很多。第二斷鏈操作別省。不管是用cur.next None還是prev.next None該斷就斷。少寫一次斷鏈可能就浪費(fèi)一小時(shí)debug。第三先跑小用例再上大用例。本地調(diào)試時(shí)先測(cè)兩個(gè)節(jié)點(diǎn)、三個(gè)節(jié)點(diǎn)、全部逆序、全部正序、全部相同值這五種小用例過(guò)了再去測(cè)長(zhǎng)的隨機(jī)鏈表。不要一上來(lái)就跑10^5的隨機(jī)數(shù)據(jù)出了問(wèn)題根本定位不到是哪一層循環(huán)的鍋。第四迭代歸并的subLength不是從0開(kāi)始而是從1開(kāi)始。從1開(kāi)始的含義是第一輪合并的是“每個(gè)長(zhǎng)度為1節(jié)點(diǎn)的有序鏈表”也就是把兩個(gè)單節(jié)點(diǎn)進(jìn)行合并。如果你從0開(kāi)始第一輪實(shí)際上沒(méi)做任何有效操作白白浪費(fèi)一次循環(huán)。這個(gè)小細(xì)節(jié)我在面試模擬時(shí)被面試官問(wèn)過(guò)一次從那以后就牢牢記住了。第五遇到超長(zhǎng)時(shí)間鏈表時(shí)優(yōu)先懷疑是循環(huán)條件出了問(wèn)題。比如while cur的內(nèi)層循環(huán)中如果有一個(gè)分支沒(méi)有正確更新cur會(huì)導(dǎo)致某個(gè)節(jié)點(diǎn)被重復(fù)處理鏈表陷入局部死循環(huán)。這種bug很難通過(guò)短用例發(fā)現(xiàn)因?yàn)槎替湵砜赡芘銮衫@過(guò)了這個(gè)分支。這也是為什么本地隨機(jī)測(cè)試要跑1000次以上覆蓋各種長(zhǎng)度和各種分布的值。最后再分享一個(gè)小技巧面試講到空間復(fù)雜度時(shí)如果你用遞歸歸并建議主動(dòng)說(shuō)“遞歸棧深度是O(log n)如果嚴(yán)格討論輔助空間它不算O(1)”——這句話說(shuō)出來(lái)其實(shí)已經(jīng)比80%的候選人強(qiáng)了。然后你再補(bǔ)一句“不過(guò)我們可以用自底向上的迭代歸并把它變成真正的O(1)”當(dāng)場(chǎng)把迭代版本甩出來(lái)這樣面試官基本就沒(méi)什么可挑的了。排序鏈表這道題每次重做都會(huì)有新的收獲至少我在寫完這篇梳理之后再遇到任何“鏈表排序”的變體都不會(huì)慌。把歸并排序吃透鏈表操作的基本功就算真正過(guò)關(guān)了。