题目描述

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

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

样例

输入：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

算法1

(暴力枚举) $O(n*k)$ ，k为链表数组长度，n为所有链表节点

两层循环，找出每次遍历的val最小值，设置为当前节点的下个节点，重置当前节点，依次循环，直到所有节点的下一个节点都为null

Java 代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        while(true){
            ListNode node=null;
            int j=-1;
            for(int i=0;i<lists.length;i++){
                if(node!=null){
                    if(lists[i]!=null&&node.val>lists[i].val){
                        node=lists[i];
                        j=i;
                    }
                }else{
                    node=lists[i];
                    j=i;
                }
            }
            if(node!=null){
                cur.next=node;
                cur=cur.next;
                lists[j]=lists[j].next;
            }else{
                break;
            }
        }
        return dummy.next;
    }
}

算法2

(堆优化版) $O(nlogk)$ ,k为链表数组长度，n为所有链表节点

暴力解法中，每次循环链表数组主要是为了得到当前链表数组中头节点中val的最小值，因此可以小顶堆进行优化

Java 代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        PriorityQueue<ListNode> queue=new PriorityQueue<>((o,n) -> o.val-n.val);
        for(int i=0;i<lists.length;i++){
            if(lists[i]!=null){
                queue.add(lists[i]);
            }
        }
        while(!queue.isEmpty()){
            ListNode node=queue.poll();
            cur.next=node;
            cur=cur.next;
            if(node!=null&&node.next!=null){
                queue.add(node.next);
            }
        }
        return dummy.next;
    }
}