目錄

題目：

示例：

分析：

代碼：

題目：

示例：

分析：

題目給我們一個鏈表數(shù)組，數(shù)組里的鏈表都是升序的，讓我們合并這些鏈表，要求合并之后還是升序的。

最簡單最直觀的做法就是遍歷整個數(shù)組，把每個鏈表的節(jié)點都取出來塞到一個容器里，然后對容器進行升序排序，接著按順序重新串連成新的鏈表就可以。

我本以為這么做有些暴力，不太好，結(jié)果：

?emmm。。。。

也沒什么不好的，最高端的食材往往只需要最簡單的烹飪方式，最困難的題目往往只需要最樸素的解法。

那除了這個取出來再排序的“暴力”解法，那還有一種就是不用我們親自去“暴力”的方法。

那就是利用小頂堆的堆頂永遠(yuǎn)是堆內(nèi)的最小元素這一特性，我們把元素全部塞進小頂堆。

接著進入while循環(huán)，只要堆不為空，那我就把堆頂取出來接到新鏈表后。

最后一樣也是可以獲取到一條升序的鏈表。

兩種解法沒什么本質(zhì)上的區(qū)別，不同的就是第一種我們手動去排序了，第二種是人家?guī)臀覀內(nèi)ヅ判蛄恕]啥本質(zhì)上的區(qū)別，運行的結(jié)果也是一樣的。

既然這種偏“暴力”的解法都還解得不錯，那么用這種“暴力”解法就好了。

如果一定要利用到原本鏈表就升序的這個特性的話，也可以。

我們先進入while循環(huán)，循環(huán)的條件是整個原數(shù)組里的鏈表至少有一個不為空指針節(jié)點。

接著進入一層for循環(huán)，去尋找數(shù)組里那個鏈表頭的值最?。ú晃ㄒ唬又阉〕鰜矸诺叫骆湵淼暮竺?，再把這個鏈表往后移動。

直到原數(shù)組里的鏈表都變成了空指針節(jié)點，那么我們就是合并完成了。

我個人覺得還不如上面的兩種“暴力”解法簡單。

不過思路提供給大家了，怎么做都可以，黑貓白貓能抓老鼠的都是好貓。文章來源地址http://www.zghlxwxcb.cn/news/detail-643866.html

代碼：

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //把節(jié)點塞到一個容器里排序后重新連接成鏈表
        vector<ListNode*>cache;
        for(auto list:lists){
            while(list){
                cache.push_back(list);
                list=list->next;
            }
        }
        sort(cache.begin(),cache.end(),[](auto a,auto b){return a->val<b->val;});
        ListNode* res=new ListNode(0);
        ListNode* cur=res;
        for(ListNode* node:cache){
            cur->next=node;
            cur=cur->next;
        }
        cur->next=nullptr;
        return res->next;
        
        //把節(jié)點塞到一個小頂堆里,然后生成鏈表
        auto cmp=[](auto a,auto b){return a->val>b->val;};
        priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)>minpq;
        for(auto list:lists){
            while(list){
                minpq.push(list);
                list=list->next;
            }
        }
        ListNode* res=new ListNode(0);
        ListNode* cur=res;
        while(!minpq.empty()){
            cur->next=minpq.top();
            minpq.pop();
            cur=cur->next;
        }
        cur->next=nullptr;
        return res->next;
    }
};

到了這里，關(guān)于【力扣每日一題】2023.8.12 合并K個升序鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！