链表系列一＞合并 k 个升序链表

题目：

链接: link

方法一解析：

代码：

public ListNode mergeKLists(ListNode[] lists) {
        //建立小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1,v2)-> v1.val - v2.val);

        //把所有头节点放入小根堆中
        for(ListNode l : lists){
            if(l != null){
                heap.offer(l);
            }
        }

        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while(!heap.isEmpty()){
            ListNode t = he

            prev.next = t;
            prev.next = t;
            prev = t;
            if(t.next != null)
                heap.offer(t.next);
        }

        return ret.next;
    }

方法二解析：

代码：

//递归写法:
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }

    public ListNode merge(ListNode[] lists,int left, int right){
        if(left > right)
            return null;
        if(left == right)
            return lists[left];    

        //1.平分数组    
        int mid = (left + right) / 2;
        //[left,mid][mid+1,right]

        //2.递归处理
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);

        //3.合并两个有序链表
       return megeToList(l1,l2);
    }

    private ListNode megeToList(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        ListNode cur1 = l1, cur2 = l2;

        while(cur1 != null && cur2 != null){
            if(cur1.val < cur2.val){
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            }else{
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
        if(cur1 != null) prev.next = cur1;
        if(cur2 != null) prev.next = cur2;

        return ret.next;
    }