LeetCode 23這道題我刷了三遍才敢說真正弄懂。題目標(biāo)題通常寫的是“合并K個升序鏈表”但不少人習(xí)慣叫它“合并K個升序鏈表的數(shù)組”——其實(shí)這兩種叫法都對因?yàn)檩斎刖褪且粋€裝著K個鏈表頭節(jié)點(diǎn)的數(shù)組C里就是vectorListNode*。題目要求很直白把K個已經(jīng)各自升序排列的鏈表合并成一個仍然升序的大鏈表。但“很直白”三個字背后串起來的考點(diǎn)可一點(diǎn)都不少。單鏈表的遍歷、數(shù)組容器的邊界處理、多路歸并的思想、優(yōu)先隊列和分治的應(yīng)用全在這道題里集中出現(xiàn)。我見過不少候選人一看到“合并K個鏈表”就條件反射開始寫兩兩合并結(jié)果復(fù)雜度聊崩了也見過有人能背出堆解法的代碼但問一句“為什么堆的空間是O(K)”就卡住。所以這篇東西不是單純給你貼一份題解而是把這題的幾種主流思路、復(fù)雜度推導(dǎo)、實(shí)現(xiàn)細(xì)節(jié)、還有本地怎么調(diào)試一次性講透。適合準(zhǔn)備校招/社招面試的開發(fā)者也適合刷題到鏈表階段想進(jìn)階多路歸并的讀者。哪怕你暫時不面試多路歸并的思想在日志合并、外部排序、分片數(shù)據(jù)匯總這些真實(shí)場景里也會反復(fù)用到。1. 題目拆解與審題陷阱很多人拿到這道題就急著寫代碼其實(shí)第一步應(yīng)該先確認(rèn)輸入形態(tài)。什么叫“合并K個升序鏈表的數(shù)組”簡單說你有一個數(shù)組數(shù)組每個元素是一個鏈表頭指針每個鏈表內(nèi)部的節(jié)點(diǎn)值從小到大排列但鏈表之間沒有任何順序保證。最終要返回一個新鏈表的頭節(jié)點(diǎn)新鏈表包含所有節(jié)點(diǎn)且整體升序。1.1 輸入到底是什么先看鏈表數(shù)組的形態(tài)用C寫就是這樣的結(jié)構(gòu)struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; vectorListNode* lists;lists可能為空數(shù)組也就是一個鏈表都沒有此時應(yīng)該返回空指針nullptr。lists里也可能有某個元素是nullptr代表那條“鏈路”不存在。各個鏈表的長度也不一定相同有的長有的短甚至有的鏈表只有一個節(jié)點(diǎn)。還有一個很容易被忽略的點(diǎn)題目要求的是“合并”不是“新建”。你不需要new出一堆新節(jié)點(diǎn)直接調(diào)整現(xiàn)有節(jié)點(diǎn)的next指針指向就行。很多人習(xí)慣性地創(chuàng)建一個新鏈表再逐個拷貝值這樣既不省事面試時還會被追問“為什么不原地操作”。1.2 三條常規(guī)路線怎么選我見過的主力解法就三種順序合并、分治合并、優(yōu)先隊列小頂堆。各自對應(yīng)著不同的思維角度。順序合并先把第一條和第二條合并得到的結(jié)果再和第三條合并一輪一輪往下滾。分治合并把K條鏈表兩兩配對先各自合并再把合并結(jié)果繼續(xù)兩兩配對直到剩一條。優(yōu)先隊列小頂堆把K條鏈表的當(dāng)前頭節(jié)點(diǎn)都丟進(jìn)一個最小堆每次彈出全局最小的節(jié)點(diǎn)然后從對應(yīng)鏈表補(bǔ)一個節(jié)點(diǎn)進(jìn)堆。這三種方法我用一個日常生活類比來解釋。假設(shè)有K個有序的隊伍每個隊伍按身高從低到高排好現(xiàn)在要合并成一個總隊伍。順序合并就是請你當(dāng)“總調(diào)度”先把前兩個隊伍合并好再拿這個結(jié)果和第三個隊伍合并分治合并就是搞“小組賽”每兩個隊伍先合并勝者進(jìn)入下一輪優(yōu)先隊列就是搞“冠軍候選池”每輪從每個隊伍隊首挑一個最矮的最后全場最小的那個人出列。三種思路沒有絕對優(yōu)劣但面試場景下分治和優(yōu)先隊列是我最推薦優(yōu)先講的。1.3 復(fù)雜度地圖假設(shè)總共有K條鏈表每條鏈表的平均長度是n總節(jié)點(diǎn)數(shù)NK×n。三個方案的時間復(fù)雜度和空間復(fù)雜度分別如下解法時間復(fù)雜度空間復(fù)雜度優(yōu)缺點(diǎn)順序合并O(K2 × n)O(1)實(shí)現(xiàn)最直白但節(jié)點(diǎn)多時非常慢分治合并O(Kn × log K)O(log K)遞歸棧穩(wěn)定手寫不容易錯面試最推薦優(yōu)先隊列O(Kn × log K)O(K)堆時間最優(yōu)但比較器細(xì)節(jié)容易寫歪為什么順序合并會到O(K2 × n)因?yàn)槊看魏喜⒑蠼Y(jié)果鏈表會變長下次再合并時就要遍歷這個已經(jīng)變長的鏈表。第一次合并遍歷約2n個節(jié)點(diǎn)第二次約3n個節(jié)點(diǎn)最后一次約Kn個節(jié)點(diǎn)加起來就是(23...K)×n量級確實(shí)在O(K2n)。這個數(shù)學(xué)推導(dǎo)是后面所有優(yōu)化的動機(jī)。2. 解法一順序合并思路最直但效率最差別小看順序合并。就算你最后決定在面試?yán)镏v分治或堆也最好能手寫一遍順序合并。它既能讓你理解“合并兩個有序鏈表”這個基礎(chǔ)操作也是一個很好的復(fù)雜度反面教材。2.1 順序合并的思路與實(shí)現(xiàn)核心邏輯就兩步寫一個mergeTwoLists函數(shù)合并兩條升序鏈表然后遍歷整個lists數(shù)組把當(dāng)前結(jié)果和下一個鏈表頭傳進(jìn)合并函數(shù)滾動更新。class Solution { public: ListNode* mergeKLists(vectorListNode* lists) { if (lists.empty()) return nullptr; ListNode* res nullptr; for (ListNode* head : lists) { res mergeTwoLists(res, head); } return res; } ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode dummy(0); ListNode* tail dummy; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return dummy.next; } };寫的時候有幾個細(xì)節(jié)要特別注意。第一dummy節(jié)點(diǎn)哨兵節(jié)點(diǎn)是鏈表題里的老演員了它的作用就是幫你省去對頭節(jié)點(diǎn)為空的單獨(dú)判斷。第二a b循環(huán)結(jié)束后一定還有一條鏈表剩余直接用tail-next a ? a : b接上不要再去while循環(huán)遍歷剩余節(jié)點(diǎn)那樣代碼會啰嗦不少還容易漏邊界。2.2 為什么面試官一定會追問你這版代碼如果你面試時只給出順序合并面試官大概率會繼續(xù)追問“這個方案的時間復(fù)雜度是多少還能再優(yōu)化嗎”這時候就看你有沒有提前算過賬。第一輪合并res是空的實(shí)際就是返回lists[0]遍歷了n個節(jié)點(diǎn)。第二輪合并res長度為2n傳入mergeTwoLists時兩個鏈表加起來要遍歷3n個節(jié)點(diǎn)。等到第K輪兩個鏈表長度分別是(K-1)n和n遍歷Kn個節(jié)點(diǎn)。所以總遍歷節(jié)點(diǎn)數(shù)大約是n×(23...K)也就是O(K2n)。當(dāng)K很大、n也很大時這個平方級的增長會讓性能急劇惡化。比如K1000、每條鏈表平均1000個節(jié)點(diǎn)順序合并跑起來非常吃力刷題平臺很容易直接超時。我之前帶過的新人經(jīng)常問“那為什么很多題解里順序合并也能過”能過的情況通常是K很小比如只有幾條鏈表或者n非常短。LeetCode的測試用例覆蓋面很廣K可以很大所以靠順序合并硬莽并不穩(wěn)妥。3. 解法二分治合并手寫最穩(wěn)的解法分治合并是我個人在面試中最推薦優(yōu)先展示的方案。因?yàn)樗乃悸非逦a穩(wěn)定性高不會被優(yōu)先隊列比較器的細(xì)節(jié)坑到。而且它和歸并排序長得幾乎一模一樣只要你對歸并排序有印象就一定能順下來。3.1 化多路為兩路分治的核心思想是不急著把所有鏈表一次性合并而是先把數(shù)組對半切開左邊一半合并成一條右邊一半合并成一條最后再合并這兩條。左半邊和右半邊的內(nèi)部又繼續(xù)用同樣的方式遞歸。這個思路可以類比“擂臺賽輪流打”和“分組淘汰賽”的區(qū)別。順序合并是讓當(dāng)前冠軍一直站在臺上每一輪都迎接一個新對手越到后面對手越強(qiáng)冠軍消耗越大分治是先把選手分成小組組內(nèi)決出勝者勝者再繼續(xù)打每輪的對手規(guī)模更均衡總比賽場次也少很多。3.2 遞歸實(shí)現(xiàn)細(xì)節(jié)與代碼分治的代碼比順序合并稍微長一點(diǎn)但核心只有兩個函數(shù)一個負(fù)責(zé)把數(shù)組區(qū)間[l, r)內(nèi)的鏈表合并起來另一個就是復(fù)用的mergeTwoLists。class Solution { public: ListNode* mergeKLists(vectorListNode* lists) { if (lists.empty()) return nullptr; return mergeRange(lists, 0, lists.size()); } ListNode* mergeRange(vectorListNode* lists, int l, int r) { if (r - l 1) return lists[l]; if (r - l 2) return mergeTwoLists(lists[l], lists[r - 1]); int mid l (r - l) / 2; ListNode* left mergeRange(lists, l, mid); ListNode* right mergeRange(lists, mid, r); return mergeTwoLists(left, right); } ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode dummy(0); ListNode* tail dummy; while (a b) { if (a-val b-val) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; } tail-next a ? a : b; return dummy.next; } };我寫這段代碼時踩過一個坑區(qū)間邊界的開閉。上面的寫法統(tǒng)一用左閉右開區(qū)間[l, r)好處是遞歸調(diào)用時天然規(guī)避了mid重復(fù)處理的問題。如果你習(xí)慣用閉區(qū)間[l, r]也能寫但基準(zhǔn)條件要改成l r時返回空、l 1 r時返回lists[l]否則很容易出現(xiàn)無限遞歸。還有一個小點(diǎn)為什么要單獨(dú)處理r - l 2其實(shí)不單獨(dú)處理也行因?yàn)閞 - l 2時mid會取到l1左區(qū)間[l, l1)遞歸返回lists[l]右區(qū)間[l1, r)遞歸返回lists[l1]再合并也是一樣的。但基準(zhǔn)條件多一點(diǎn)遞歸深度會少一層也能避免讀者看到mergeRange里同時出現(xiàn)lists[l]和lists[l1]時的困惑。我習(xí)慣把這兩種情況都顯式寫出來可讀性更好。3.3 復(fù)雜度推演分治合并的時間復(fù)雜度推導(dǎo)非常漂亮。每一輪合并所有鏈表都會被兩兩結(jié)對每一對合并的代價是兩條鏈表的長度和。第一輪有K/2對每對合并長度2n總代價Kn第二輪有K/4對每對長度4n總代價還是Kn。每一輪總代價都是Kn一共有l(wèi)ogK輪所以總代價是Kn×logK?？臻g復(fù)雜度主要看遞歸棧深度是O(logK)比優(yōu)先隊列的O(K)更省。當(dāng)然如果你用迭代方式兩兩合并可以做到O(1)的額外空間但代碼會稍微繞一點(diǎn)。我自己刷題時更喜歡遞歸版本邏輯一目了然面試時手寫不容易慌。4. 解法三優(yōu)先隊列用最小的堆空間做全局歸并優(yōu)先隊列解法是時間效率上的最優(yōu)解之一也是很多語言內(nèi)置數(shù)據(jù)結(jié)構(gòu)展示“優(yōu)雅”的絕佳例子。但它在C里有一個經(jīng)典陷阱priority_queue默認(rèn)是大頂堆而且自定義比較器的語義反直覺很多人寫錯了還不知道。4.1 為什么想到用小頂堆回憶一下mergeTwoLists的過程每次比較兩條鏈表的頭節(jié)點(diǎn)誰小誰出列?，F(xiàn)在變成K條鏈表其實(shí)也是一樣——比較K個頭節(jié)點(diǎn)選最小的那個出列。但如果每次都線性掃描K個頭節(jié)點(diǎn)找最小值時間復(fù)雜度會變成O(KN)那就沒有必要了。這里就是堆的主場。小頂堆可以在O(logK)時間內(nèi)完成“取最小”和“插入新元素”兩個操作。我們把K條鏈表的當(dāng)前頭節(jié)點(diǎn)都放進(jìn)堆堆頂就是全局最小節(jié)點(diǎn)彈出堆頂再把該節(jié)點(diǎn)的next節(jié)點(diǎn)入堆一路循環(huán)到堆為空所有節(jié)點(diǎn)就按升序串起來了。4.2 priority_queue 的坑與完整實(shí)現(xiàn)C里寫最小堆優(yōu)先隊列最容易翻車的是比較器。std::priority_queue的第三個模板參數(shù)是一個比較器但這個比較器不是直接表達(dá)“誰小誰優(yōu)先”而是表達(dá)“誰應(yīng)該排在后面”。默認(rèn)的less會把大元素放在前面所以你要反轉(zhuǎn)比較邏輯讓值更大的節(jié)點(diǎn)被認(rèn)為“排后面”堆頂才會是最小節(jié)點(diǎn)。class Solution { public: ListNode* mergeKLists(vectorListNode* lists) { auto cmp [](ListNode* a, ListNode* b) { return a-val b-val; // 注意這里是大于號 }; priority_queueListNode*, vectorListNode*, decltype(cmp) pq(cmp); for (ListNode* head : lists) { if (head) pq.push(head); } ListNode dummy(0); ListNode* tail dummy; while (!pq.empty()) { ListNode* cur pq.top(); pq.pop(); tail-next cur; tail cur; if (cur-next) pq.push(cur-next); } return dummy.next; } };這段代碼里最關(guān)鍵的就是return a-val b-val。很多第一次寫的人會下意識寫a-val b-val結(jié)果發(fā)現(xiàn)堆頂變成了最大值鏈表順序全反了。我的經(jīng)驗(yàn)是在C的priority_queue里greater對應(yīng)小頂堆less對應(yīng)大頂堆如果你想用lambda就要把邏輯寫成“值更大的節(jié)點(diǎn)優(yōu)先級更低”。另外要注意初始化堆時不能把空指針放進(jìn)去。for循環(huán)里的if (head)就是在過濾空鏈表。在彈出節(jié)點(diǎn)后也要先檢查cur-next是否為空為空就不需要再入堆了否則空指針進(jìn)堆會導(dǎo)致運(yùn)行時錯誤。4.3 三種解法怎么選如果面試官讓你只寫一種我的建議是優(yōu)先隊列最不容易被后續(xù)追問卡死——因?yàn)樗日故玖四銓Χ褦?shù)據(jù)結(jié)構(gòu)的掌握又直觀體現(xiàn)了O(logK)的選擇復(fù)雜度。但如果面試現(xiàn)場氣氛比較緊張或者你對C的priority_queue比較器不夠自信分治合并是更穩(wěn)妥的選擇。它不依賴heap的語義陷阱只要會把區(qū)間二分就能寫對。順序合并也不是不能提但你最好主動說出它的復(fù)雜度問題然后順勢引出優(yōu)化方案。這樣反而能給面試官留下“這人有復(fù)雜度意識”的好印象。千萬不要只丟一個順序合并上去就停下來那大概率會被認(rèn)為算法功底不夠扎實(shí)。5. 真實(shí)場景、調(diào)試經(jīng)驗(yàn)與面試實(shí)戰(zhàn)很多人刷算法題刷完就忘覺得“這題面試過了就行”。但LeetCode 23背后的多路歸并思路在真實(shí)工程里出現(xiàn)頻率很高把它理解到位價值遠(yuǎn)不止應(yīng)付一場面試。5.1 這題在真實(shí)業(yè)務(wù)里到底有什么用最典型的場景是外部排序。當(dāng)數(shù)據(jù)量大到內(nèi)存裝不下時會把大文件切分成多個可以載入內(nèi)存的小文件每個小文件內(nèi)部排好序然后就需要把這些有序文件合并成一個更大的有序文件。你可以把每個小文件想象成一條“鏈表”文件指針就是鏈表的next用小頂堆逐條取出最小值寫入輸出文件這就是堆解法在磁盤IO場景下的直接應(yīng)用。另一個常見場景是日志歸并。微服務(wù)架構(gòu)下同一個用戶請求的日志可能分散在多個服務(wù)節(jié)點(diǎn)上每臺機(jī)器按時間戳本地有序。排查問題時要把所有日志按時間順序聚合這就是典型的多路歸并。我自己就經(jīng)常寫類似的腳本只是語言從C換成了Python但核心數(shù)據(jù)結(jié)構(gòu)還是堆。還有分庫分表后的數(shù)據(jù)匯總、多路有序流合并、K路有序數(shù)組合并本質(zhì)上都是這題的變體。所以我才說這題值得多花點(diǎn)時間把它徹底弄明白而不是背個代碼就完事。5.2 本地調(diào)試怎么造鏈表測試數(shù)據(jù)刷題平臺會幫你構(gòu)造好鏈表數(shù)組但本地調(diào)試時你得自己寫工具函數(shù)。我發(fā)現(xiàn)很多人卡在“不會造測試數(shù)據(jù)”反而影響了排錯效率。這里分享一個我常用的快速構(gòu)造方式ListNode* makeList(initializer_listint vals) { ListNode dummy(0); ListNode* tail dummy; for (int v : vals) { tail-next new ListNode(v); tail tail-next; } return dummy.next; } void printList(ListNode* head) { while (head) { cout head-val - ; head head-next; } cout null endl; } vectorListNode* lists { makeList({1, 4, 5}), makeList({1, 3, 4}), makeList({2, 6}) }; printList(mergeKLists(lists));在本地調(diào)試時我強(qiáng)烈建議你專門試幾組邊界數(shù)據(jù)空的lists、只有一個元素的lists、包含空鏈表的lists、所有鏈表都只有一個節(jié)點(diǎn)的lists。這些邊界情況在面試手寫代碼時最容易翻車提前在本地跑一遍腦子里的邊界感會強(qiáng)很多。我自己踩過的坑是本地構(gòu)造鏈表時用了裸new程序結(jié)束沒有釋放內(nèi)存雖然不影響刷題但如果你用Valgrind或ASan檢查會報內(nèi)存泄漏。面試寫題不用糾結(jié)內(nèi)存釋放但平時練習(xí)可以順手在析構(gòu)函數(shù)里清理養(yǎng)成好習(xí)慣。5.3 面試?yán)镌趺创鸬闷撩嬖嚬賿伋鲞@道題時建議你不要悶頭就寫。先花30秒把思路說清楚“這道題可以用順序合并但復(fù)雜度是O(K2n)我傾向于用分治合并先把數(shù)組二分遞歸合并再兩兩merge或者用一個小頂堆每次取K個頭節(jié)點(diǎn)里的最小值堆解法時間也是O(Kn logK)但空間略大?！边@個開場白的好處是你已經(jīng)主動展示了復(fù)雜度意識、方案對比能力面試官后續(xù)大概率不會揪著基礎(chǔ)細(xì)節(jié)窮追猛打而是會順著你的思路深入到某一個方案里聊。常見變體題也值得提前準(zhǔn)備。如果輸入不是鏈表數(shù)組而是K個有序數(shù)組讓你返回一個合并后的大數(shù)組解法思路完全一樣只是把next指針換成數(shù)組下標(biāo)加一。如果K特別大、但每個鏈表的節(jié)點(diǎn)數(shù)特別少堆解法就會更有優(yōu)勢因?yàn)榉种蔚倪f歸深度logK也會增大。如果鏈表節(jié)點(diǎn)帶額外字段合并時就需要自定義比較邏輯這時候優(yōu)先隊列的cmp就比普通值比較更適合擴(kuò)展。最后一個建議別只聽我說自己把三種解法都寫一遍跑同一組測試數(shù)據(jù)對比耗時和內(nèi)存。不用太糾結(jié)具體數(shù)值重點(diǎn)是感受不同方案在K增大時的曲線差異。等你親手體會到順序合并變卡、分治和堆依然穩(wěn)這題才算真正吃透了。根據(jù)我個人的刷題經(jīng)驗(yàn)LeetCode 23是“一道題頂五道題”的典型代表。它把鏈表操作、數(shù)組邊界、分治思想、堆的應(yīng)用全部串在一起而且每個解法都能聊出深度。面試前花一個晚上把順序合并、分治合并、優(yōu)先隊列三種寫法都練熟比刷十道簡單鏈表題都管用。我到現(xiàn)在偶爾去面試候選人遇到這道題時最欣慰的并不是對方把代碼寫出來而是能把“為什么選堆”“空間復(fù)雜度是多少”“真實(shí)場景里怎么用”也講清楚。希望你也能達(dá)到這個狀態(tài)。