23-合并k个升序链表

LeetCode 23. Merge k Sorted Lists

LeetCode-23

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

method: 小根堆

把链表的值和序号放进小根堆排序，会按照值的大小从小到大排序，然后通过序号找到是哪条链表的，如果他还有值，就继续插入堆中

ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode *dummy = new ListNode(0);
    ListNode *head = dummy;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    for (int i = 0; i < lists.size(); i++) {   // 先把每条链的头结点放进来
        if (lists[i]) q.push(pair(lists[i]->val, i));
    }
    while (!q.empty()) {
        int index = q.top().second; // 取序号
        q.pop();
        head->next = lists[index];
        head = head->next;
        lists[index] = lists[index]->next;  // 序号链表移动
        if (lists[index]) q.push(pair(lists[index]->val, index));
        // 如果还有就继续放入
    }
    return dummy->next;
}

时间复杂度：优先队列中的元素不超过$k$个，插入删除的时间复杂度是$O(logk)$，每个元素插入删除一次，总共$kn$个元素，所以渐进时间复杂度是$O(kn \times logk)$
空间复杂度：优先队列中的元素不超过$k$个，所以渐进空间复杂度为$O(k)$