老师,我在听课之前,自己先想了下,试着写了一个算法,但是我不清楚哪里有问题,leeCode一直报错
来源:10-5 LeetCode:23. 合并K个排序链表
慕侠4287760
2020-10-10
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,
还请老师帮忙解答
写回答
1回答
-
这个错误其实是说你的引用类型形成了一个循环。也就是说你的链表可能是一个圈儿。你打印一下你链表的变化,看一下哪一步逻辑错误导致它出现了一个循环引用。
012020-10-12
相似问题