题解 | #合并k个已排序的链表#

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void quickSort(ListNode[] arr,int k){
        quick(arr,0,k-1);
    }
    public void quick(ListNode[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int privot=parttion(arr,left,right);
        quick(arr,left,privot-1);
        quick(arr,privot+1,right);
        
    }
    private int parttion(ListNode[] arr,int left,int right){
        ListNode priovt=arr[left];
        while(left<right){
            while(left<right&&arr[right].val>=priovt.val){
                right--;
            }
            arr[left]=arr[right];
            while(left<right&&arr[left].val<=priovt.val){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=priovt;
        return left;
    }
    public boolean isfull(ListNode[] arr,int k){
        return k==arr.length;
    }
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        ListNode ret=null;
        int len=lists.size();
        ListNode[] arr=new ListNode[10];
        int k=0;
        for(int i=0;i<len;i++){
            ListNode cur=lists.get(i);
            while(cur!=null){
                if(isfull(arr,k)){
                    arr=Arrays.copyOf(arr,arr.length*2);
                }
                arr[k]=cur;
                k++;
                cur=cur.next;
            }
        }
        for(int i=0;i<k;i++){
            arr[i].next=null;
        }
        quickSort(arr,k);
        ret=arr[0];
        ListNode cur=ret;
        for(int i=1;i<k;i++){
            cur.next=arr[i];
            cur=cur.next;
        }



        return ret;

    }
}