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

/*

• function ListNode(x){
• this.val = x;
• this.next = null;
• } */

/** *

• @param lists ListNode类一维数组
• @return ListNode类 */

function swap(arr,i,j){
    if(i===j) return;
    const temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}

function partition(arr,pivot,left,right){
    const pivotValue=arr[pivot];
    let startIndex=left;
    for(let i=left;i<right;i++){
        if(arr[i]<pivotValue){
            swap(arr,i,startIndex);
            startIndex++;
        }
    }
     swap(arr,startIndex,pivot);
    return startIndex;
}

function quickSort(arr,left,right){
  
    if(left<right){
        const pivot=right;
        const partitionIndex=partition(arr,pivot,left,right);
        quickSort(arr,left,partitionIndex-1);
        quickSort(arr,partitionIndex+1,right)
    }
}

function mergeKLists( lists ) {
    // write code here
   const arr=[];
   for(let list of lists){
       let node=list;
       while(node){
           arr.push(node.val);
           node=node.next;
       }
   }
    
//    arr.sort((a,b)=>a-b);
    
   quickSort(arr,0,arr.length-1);// 原地排序
    
   const newListNode=new ListNode(-1);
   let dummyNode= newListNode;
    
    for(let num of arr){
        dummyNode.next=new ListNode(num);
        dummyNode=dummyNode.next;
    }
    
    return newListNode.next;
}

module.exports = { mergeKLists : mergeKLists };