Merging K Sorted Linked Lists 算法问题，史上最难的问题来自 LeetCode

代码实现

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //用heap(堆)这种数据结构，也就是 java 里面的 PriorityQueue
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode a, ListNode b) {
                return a.val-b.val;
            }
        });
        ListNode ret = null, cur = null;
        for(ListNode node: lists) {
            if(null != node) {
                pq.add(node);    
            }
        }
        while(!pq.isEmpty()) {
            ListNode node = pq.poll();
            if(null == ret) {
                ret = cur = node;
            }
            else {
                cur = cur.next = node;
            }
            if(null != node.next) {
                pq.add(node.next);    
            }
        }
        return ret;
    }
}
复制代码

问题分析2

这道题需要合并k有序链表，最终的合并结果也必须是有序的。如果一开始没有线索，可以从一个简单的开始：合并两个有序链表。

合并两个有序链表：将两个有序链表合并为一个新的有序链表并返回。新的链表是通过连接两个给定链表的所有节点形成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
复制代码

这道题，就按照描述来：创建一个新的链表，比较原来两个链表中的元素值，将较小的链接到新的链表中。需要注意的一点是，由于两个输入链表的长度可以不同，最终一个链表会先完成所有元素的插入，另一个未完成的链表会直接链接到新链表的末尾。

所以代码实现很容易写：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //新建链表
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        // 注意点：当有链表为空时，直接连接另一条链表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return dummyHead.next;
    }
复制代码

现在回到原来的主题：合并K个排序链表。

合并 K 个有序链表 和 合并两个有序链表 之间的区别在于必须工作的有序链表的数量，以便完全可以合并 K 个有序链表以上代码思路。链接列表。

这里可以参考**归并排序**的分治思想，首先将这K个链表拆成两个K/2个链表，处理它们的合并，然后继续划分，直到拆分为仅一个或两个链表中的任务开始合并。

代码实现

根据上面的动画来看，实现代码非常简单易懂。先分裂，直到不能分裂为止，然后开始合并。

class Solution {
    public ListNode mergeKLists(ListNode[] lists){
        if(lists.length == 0)
            return null;
        if(lists.length == 1)
            return lists[0];
        if(lists.length == 2){
           return mergeTwoLists(lists[0],lists[1]);
        }

        int mid = lists.length/2;
        ListNode[] l1 = new ListNode[mid];
        for(int i = 0; i < mid; i++){
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length-mid];
        for(int i = mid,j=0; i < lists.length; i++,j++){
            l2[j] = lists[i];
        }

        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

作者：程序员吴哥
链接：https://juejin.im/post/5cabeaa4e51d456e2446fc62
来源：掘金版权归作者所有。商业转载请联系作者获取授权。非商业转载请注明出处。