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