题解 | #合并k个已排序的链表#

合并k个已排序的链表

https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

两个时间复杂度低（O(nklogk)）且容易理解的方法：分层合并 && 优先队列

1.分层合并：

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* head1, ListNode* head2)
    {
        if(!head1 || !head2) return head1 ? head1 : head2;
        ListNode* dummy = new ListNode(0);
        ListNode* tmp = dummy, * tmp1 = head1, * tmp2 = head2;
        while(tmp1 && tmp2)
        {
            if(tmp1 -> val < tmp2 -> val)
            {
                tmp -> next = tmp1;
                tmp1 = tmp1 -> next;
            }
            else
            {
                tmp -> next = tmp2;
                tmp2 = tmp2 -> next;
            }
            tmp = tmp -> next;
        }
        tmp -> next = tmp1 ? tmp1 : tmp2;
        return dummy -> next;
    }
    
    
    ListNode* merge(vector<ListNode *> &lists, int l, int r)
    {
        if(l > r) return nullptr;
        if(l == r) return lists[l];
        int mid = l + r >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        //1.逐个合并：O(k^2*n)
        //2.分组合并：O(nklogk)
        //3.小根堆合并：O(nklogk)
        return merge(lists, 0, lists.size() - 1);
    }
};

2：小根堆合并

class Solution {
public:
    struct Node{
        int val;
        ListNode* head;
        bool operator < (const Node& W) const
        {
            return val > W.val;
        }
    };
    priority_queue<Node> q; //自定义数据类型一定要指定(重载)排序规则
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        for(auto list : lists)
            if(list) q.push({list -> val, list}); //加入所有链表的头结点
        ListNode* dummy = new ListNode(0);
        ListNode* tmp = dummy;
        
        while(q.size())
        {
            auto t = q.top(); q.pop();
            tmp -> next = t.head;
            tmp = tmp -> next;
            if(t.head -> next) 
                q.push({t.head -> next -> val, t.head -> next});
        }
        return dummy -> next;
    }
};