题解 | #反转链表#

可以说是最笨的建堆操作，然后堆调整，取出堆中的数据进行插入

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

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
class Minheap{
    constructor(){
        this.heap =[];
    }
    parentNode(index){
        return (index-1)>>1;
    }
    leftNode(index){
        return index * 2+1;
    }
    rightNode(index){
        return index *2 +2;
    }
    shiftUp(index){
        if(index === 0) return;
        let parent = this.parentNode(index);
        if(this.heap[parent] && this.heap[index].val < this.heap[parent].val){
            [this.heap[parent],this.heap[index]]=[this.heap[index],this.heap[parent]];
            this.shiftUp(parent);
        }
    }
    shiftDown(index){
        
        let left = this.leftNode(index);
        let right = this.rightNode(index);
        if(this.heap[left] && this.heap[left].val < this.heap[index].val){
            [this.heap[left],this.heap[index]]=[this.heap[index],this.heap[left]];
            this.shiftDown(left);
        }
        if(this.heap[right] && this.heap[right].val < this.heap[index].val){
            [this.heap[right],this.heap[index]]=[this.heap[index],this.heap[right]];
            this.shiftDown(right);
        }
    }
    insert(node){
        this.heap.push(node);
        this.shiftUp(this.heap.length - 1);
    }
    delete(){
        if(this.size() === 1) return this.heap.shift();
        let top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
        return top;
    }
    size(){
        return this.heap.length;
    }
    
}
function sortInList( head ) {
    // write code here
    if(!head){return null}
    if(head.next == null) {return head;}
    let p = head;
    let heap = new Minheap();
    let l3 = new ListNode(-1);
    let p3 = l3;
  //建堆
    while(p){
        heap.insert(p);
        p = p.next;
    }
    console.log(heap)
  //堆中的数据拿出来，构建新链表
    while(heap.size()){
        let top = heap.delete();
        p3.next = top;
        p3 = p3.next;
    }
    //断链操作！很重要 不然会无限套娃
    p3.next = null;
    return l3.next;
}
module.exports = {
    sortInList : sortInList
};