23. 合并K个升序链表

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例.png

class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
       //0.边界处理
       if(lists==null||lists.length==0) return null;
       //1.合并
       return merge(lists,0,lists.length-1);
    }

    private ListNode merge(ListNode[] lists,int left,int right) {
        //1.索引相等直接返回
        if(left==right) return lists[left];
        //2.两两合并链表
        int mid = left + ((right-left)>>1);
        ListNode l1 = merge(lists,left,mid);
        ListNode l2 = merge(lists,mid+1,right);
        return mergeTwoLists(l1,l2);
    }

    private ListNode mergeTwoLists(ListNode l1,ListNode l2) {

       if(l1==null) return l2;
       if(l2==null) return l1;
       //虚拟头结点
       ListNode dummyHead = new ListNode();
       ListNode tailNode = dummyHead;
       //两个链表都不能为空
       while(l1 != null && l2 !=null) {
            if(l1.val < l2.val){
                tailNode.next = l1;
                tailNode = l1;
                l1 = l1.next;
            }else {
                tailNode.next = l2;
                tailNode = l2;
                l2 = l2.next;
            }
       }

       //有其中一个遍历完了，拼接起来
       tailNode.next = l1==null?l2:l1;
       
       return dummyHead.next;

    }

}