跳转至

23 合并K个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists/description/

本题在21 合并两个升序链表的基础上进行加难

解法一:顺序合并

每相邻两个合并升序链表

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
private:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
        ListNode* head = new ListNode();
        ListNode* tail = head;
        while(list1 != nullptr && list2 != nullptr){
            if(list1->val < list2->val){
                tail->next = list1;
                list1 = list1->next;
            }
            else{
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        tail->next = list1 == nullptr ? list2 : list1;
        return head->next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans = nullptr;
        for(int i = 0; i < lists.size(); i++){
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

解法二: 分治合并

类似于快速排序,分组合并

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
private:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
        ListNode* head = new ListNode();
        ListNode* tail = head;
        while(list1 != nullptr && list2 != nullptr){
            if(list1->val < list2->val){
                tail->next = list1;
                list1 = list1->next;
            }
            else{
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        tail->next = list1 == nullptr ? list2 : list1;
        return head->next;
    }
    ListNode* merge(vector<ListNode*>& lists,int l, int r){
        if(l == r)
            return lists[l];
        if(l > r)
            return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

解法三:优先级队列

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    struct cmp{
        bool operator()(const ListNode* p1, const ListNode* p2){
            // 小根堆
            return p1->val > p2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummyNode = new ListNode(-1);
        ListNode* p = dummyNode;
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        for(ListNode* head : lists){
            if(head != nullptr)
                heap.push(head);
        }
        while(!heap.empty()){
            // 取出值最小的链表头
            ListNode* head = heap.top();
            heap.pop();
            // 去掉尾部,防止产生环
            ListNode* nxt = head->next;
            head->next = nullptr;
            // 插入到新链表中
            p->next = head;
            p = p->next;
            // 更新链表头到heap
            if(nxt != nullptr)
                heap.push(nxt);
        }
        return dummyNode->next;
    }
};

复杂度分析:

时间复杂度: picture 0