Merge K ascending linked lists

Here's an array of linked lists , Each list has been listed in ascending order .

Please merge all the linked lists into one ascending list , Return the merged linked list .

Input ：
lists = [[1,4,5],[1,3,4],[2,6]]
Output ：[1,1,2,3,4,4,5,6]
explain ： The linked list array is as follows ：
[ 1->4->5, 1->3->4, 2->6 ] Combine them into an ordered list to get .
1->1->2->3->4->4->5->6

Method 1 ： Violence solution
I have done the ascending arrangement of two linked lists before , This time it is n individual , So you can use the function written before , Then go through it one by one, and then close it up , If there is too much data , The running time must exceed , Take a look 200ms.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        ListNode listsum = null;
         int len = lists.length;
         for(int i=0;i<len;i++){
    
             listsum = Merge(listsum,lists[i]);
         }
        return listsum;
    }
    public ListNode Merge(ListNode list1,ListNode list2){
    
        if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        if(list1.val<list2.val){
    
            list1.next=Merge(list1.next,list2);
            return list1;
        }
        else{
    
            list2.next=Merge(list1,list2.next);
            return list2;
        }
    }
}

Method 2 ：
Divide and conquer ：

The picture comes from Li Kou

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
    
        if(lists.length==0)
            return null;
        if(lists.length==1)
            return lists[0];
        int len = lists.length;
        int mid = len/2;
        ListNode []list1 = new ListNode[mid];
        for(int i=0;i<mid;i++)
            list1[i] =lists[i];
        ListNode []list2 =  new ListNode[len-mid];
        for(int i=0,j=mid;j<len;j++,i++)
            list2[i]=lists[j];
        return Merge(mergeKLists(list1),mergeKLists(list2));
        

    }
    public ListNode Merge(ListNode list1,ListNode list2){
    
        if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        if(list1.val<list2.val){
    
            list1.next=Merge(list1.next,list2);
            return list1;
        }
        else{
    
            list2.next=Merge(list1,list2.next);
            return list2;
        }
    }
}