合并k个有序链表

23. 合并K个排序链表

1.想法

不能每一个都进行比较那么比较合适是的归并排序
每次都两两合并,和归并排序的流程一样

2.代码

 public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0)return null;
        ListNode result = mergeMyKLists(lists,0,lists.length-1);
        return result;
    }

private ListNode mergeMyKLists(ListNode[] lists, int left, int right) {
         if(left==right)return lists[left];
        //分左右两个ListNode
        ListNode leftNodes = mergeMyKLists(lists, left, (right - left) / 2 + left);
        ListNode rightNodes = mergeMyKLists(lists, (right - left) / 2 + left + 1, right);

       //合并左右两个ListNode
        if(leftNodes == null)return rightNodes;
        if(rightNodes == null)return leftNodes;

        ListNode newNode = null;
        if(leftNodes.val<rightNodes.val){
            newNode = new ListNode(leftNodes.val);
            leftNodes = leftNodes.next;
        }else{
            newNode = new ListNode(rightNodes.val);
            rightNodes = rightNodes.next;
        }
        ListNode newHead = newNode;
        while(leftNodes!=null&&rightNodes!=null){
            if(leftNodes.val<rightNodes.val){
                newHead.next=new ListNode(leftNodes.val);
                leftNodes = leftNodes.next;
            }else{
                newHead.next=new ListNode(rightNodes.val);
                rightNodes = rightNodes.next;
            }
            newHead = newHead.next;
        }
        if(leftNodes!=null){
            newHead.next = leftNodes;
        }
        if(rightNodes!=null){
            newHead.next = rightNodes;
        }
        return newNode;
    }