算法思路

在LeetCode 21. 合并两个有序链表中介绍了如果通过双路归并合并两个有序链表，该题要求对多个链表进行归并操作。 其实和双路归并思路类似，我们分别用指针指向该链表的头结点，每次找到这些指针中值最小的结点，然后依次串联起来，并不断移动指针。

这里遇到的一个问题就是要如何找到一堆数中的最小值，这里可以利用小根堆来实现，同时我们在找到最小值结点，将其串联起来后，需要将指向该结点的指针向后移动。所以我们在堆中存储的是一对pair，其中第一个值就是指针指向的值，第二个值为当前指针。当每个元素在小根堆中排序时，默认根据第一维，即对每个指针指向结点的值进行排序。

对于小根堆的实现：

方法一：声明时加入参数

std::priority_queue<int, std::vector<int>, std::greater<int>>

方法二： 存储值的时候直接存储本来需要存储值的相反数，然后使用默认的大根堆

C ++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<pair<int, ListNode*>> heap;

        for (auto list : lists)
           if(list) heap.push({-list -> val, list});

        ListNode* dummy = new ListNode(-1);
        auto cur = dummy;

        while (heap.size())
        {
            auto t = heap.top();
            heap.pop();
            cur = cur -> next = t.second;
            auto p = t.second -> next;
            if (p) heap.push({-p -> val, p}); 
        }

        cur -> next = NULL;
        return dummy -> next;
    }
};