请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

老师,我在听课之前,自己先想了下,试着写了一个算法,但是我不清楚哪里有问题,leeCode一直报错

回答1 浏览88 2020-10-10 20:46:36

class MinHeap{
  constructor() {
    this.heap =[];
  }
  getParentIndex(i){
    return (i-1) >> 1;// 二进制
  }
  getLeftIndex(i){
    return i*2 +1;
  }
  getRightIndex(i){
    return i*2+2;
  }
  shiftUp(index){
    if(index === 0) { return;}
    const parentIndex = this.getParentIndex(index);
    if(this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val){
        this.swap(parentIndex, index);
        this.shiftUp(parentIndex);
    }  
  }
  swap(i1, i2){
    const temp = this.heap[i1];
    this.heap[i1]= this.heap[i2];
    this.heap[i2] = temp;
  }
  insert(value){
    this.heap.push(value);
    this.shiftUp(this.heap.length -1);
  }
  pop(){
    if(this.heap.length === 1 ) return this.heap.shift();
    const tmp = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return tmp;
  }
  shiftDown(index){
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    if(this.heap[leftIndex] && this.heap[leftIndex].val< this.heap[index].val){
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
    }
    if(this.heap[rightIndex] && this.heap[rightIndex].val< this.heap[index].val){
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex);
    }
  }
  peek(){
    return this.heap[0];
  }
  size(){
    return this.heap.length;
  }
}
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */

var mergeKLists = function(lists) {
    if(lists.length === 0) {
        return new ListNode(0).next;
    };
    const h = new MinHeap();
    for(let i = 0; i< lists.length; i ++){
            let p = lists[i];
            while(p){
                if(p.val){
                    h.insert(p);
                }
                p = p.next;
            }    
    }
    if(h.size() === 0) {
        return lists[0];
    }
    let head = new ListNode(0);
    let p = head;
   
    while(h.size()){
        const n = h.pop();
        console.log(n.val)
        p.next = n;
        p = p.next; 
    }
    return head.next
   
};

我主要就是想把所有元素遍历出来,都先加到最小推里面,然后一个个pop出来,但如果有同样的元素的时候就会出现,百思不得齐解
error - Found cycle in ListNode,
还请老师帮忙解答
图片描述

添加回答

已采纳回答

这个错误其实是说你的引用类型形成了一个循环。也就是说你的链表可能是一个圈儿。你打印一下你链表的变化,看一下哪一步逻辑错误导致它出现了一个循环引用。

2020-10-12 10:03:55

JavaScript版数据结构与算法 轻松解决前端算法面试

难度中级
时长15小时
人数814
好评度99.4%

夯实算法基础,填补技术短板,助力面试考题最后一公里

讲师

lewis Web前端工程师

曾就职于奇虎360、中科院计算所,现任BAT资深工程师,在React、Node.js、人工智能等领域具有丰富的开发经验。讲课深入浅出、旁征博引,极具个人风格。

意见反馈 帮助中心 APP下载
官方微信