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

合并k个已排序的链表

http://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

/*

  • 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 };

全部评论

相关推荐

06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
07-07 10:44
青岛工学院 Java
机械打工仔:对方没做错任何事,你自己在这自找没趣呢,就算他工资不高,人家定多少薪资是人家的事,况且人家写了1~3年清清楚楚
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务