精选力扣500题第18题 LeetCode 23. 合并K个升序链表【c++详细题解】

╰+哭是因爲堅強的太久メ 2021-07-24 22:25 290阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

**示例 1：**

输入：lists = [[1,4,5],[1,3,4],[2,6]]
    输出：[1,1,2,3,4,4,5,6]
    解释：链表数组如下：
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    将它们合并到一个有序链表中得到。
    1->1->2->3->4->4->5->6

**示例 2：**

输入：lists = []输出：[]

**示例 3：**

输入：lists = [[]]输出：[]

**提示：**

*  `k == lists.length`
 *  `0 <= k <= 10^4`
 *  `0 <= lists[i].length <= 500`
 *  `-10^4 <= lists[i][j] <= 10^4`
 *  `lists[i]`按 升序 排列
 *  `lists[i].length`的总和不超过 `10^4`

### 2、思路 ###

*  1、一开始先用小根堆存储`k`个排序链表的头指针，每次操作后用小根堆维护`k`个链表当前元素最小的指针，并以指针对应的值进行排序
 *  2、操作过程中，当小根堆不为空时，堆顶元素即当前`k`个排序链表当前最小的元素的指针`t`，将该值加入到`dummy`链表的后面，并把t指针往后走一位，使得`t`指针指向的值变大，再加入到小根堆中

### 3、代码 ###

* Definition for singly-linked list.
     * struct ListNode { 
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) { }
     * };
     */
    class Solution { 
    public:
    
        struct Cmp { 
            bool operator() (ListNode* a, ListNode* b) { 
                return a->val > b->val;
            }
        };
    
        ListNode* mergeKLists(vector<ListNode*>& lists) { 
            priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
            auto dummy = new ListNode(-1), tail = dummy;
            for (auto l : lists) if (l) heap.push(l);
    
            while (heap.size()) { 
                auto t = heap.top();
                heap.pop();
    
                tail = tail->next = t;
                if (t->next) heap.push(t->next);
            }
    
            return dummy->next;
        }
    };

**原题链接：**[23. 合并K个升序链表][23. _K]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[23. _K]: https://leetcode-cn.com/problems/merge-k-sorted-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/7e5fe7ae041f4b878fa75aa3d3db5aa6.png