class LinkedListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
let head = new LinkedListNode("head");
let x = [1, 1, 1, 1, 4, 10, 10, 3, 10, 9, 5, 5, 5, 8];
for (let ele of x) {
let y = new LinkedListNode(ele);
let pointer = head;
while (pointer.next != null) {
pointer = pointer.next;
}
pointer.next = y;
}
有人可以解释为什么以下"解决方案"会导致无限循环吗?
let removeDup = function(sll) {
let array = []
let pointer = sll;
while (pointer) {
if (array.includes(pointer.value)){
} else {
array.push(pointer.value);
sll.next = pointer;
sll = sll.next;
}
pointer = pointer.next;
}
}
看来,如果我
let pointer = sll.next;
或
let array = [sll.value]
然后它工作正常,但如果我按原样运行它,那么它会导致无限循环。我可以看到为什么它可能会制作一个链表,其中包含第一个值的 2 个重复项,但我不明白为什么它会进行无限循环。或者,如果有人可以指出我调试的正确方向,那也将不胜感激!
看起来您最终定义了一个在 else 条件中引用自身的节点。
您可能正在寻找这样的东西:
class LinkedListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
let head = new LinkedListNode("head");
let x = [1, 1, 1, 1, 4, 10, 10, 3, 10, 9, 5, 5, 5, 8];
for (let ele of x) {
let y = new LinkedListNode(ele);
let pointer = head;
while (pointer.next != null) {
pointer = pointer.next;
}
pointer.next = y;
}
function removeDup(currentNode = sll) {
const seen = {};
let lastUnique;
while (currentNode) {
if (seen[currentNode.value]) {
lastUnique.next = currentNode.next;
} else {
seen[currentNode.value] = true;
lastUnique = currentNode;
}
currentNode = currentNode.next;
}
}
removeDup(head);
let outputNode = head;
while (outputNode) {
outputNode = outputNode.next;
if (outputNode) {
console.log(outputNode.value);
}
}
- 如何调查你的错误
您可以使用调试器,但对于像我这样的原始人,您也可以使用控制台.log
- 在无限循环的情况下,你想要的是挣脱
let count = 0
while (pointer && count++<5) {
//whatever
}
即使你的算法失败了,你仍然会退出
- 输出变量
在你认为合适的地方发挥创意和垃圾邮件控制台.log。 放一些字符串来提醒你输出了什么垃圾
while (pointer) {
if (array.includes(pointer.value)){
console.log('cached skip')
} else {
console.log('pointervalue', pointer.value)
array.push(pointer.value);
sll.next = pointer;
sll = sll.next;
console.log('sllendloop', sll)
}
pointer = pointer.next;
}
- 修复代码
注意:不要使用数组进行缓存,因为它是 O(n( 外观
您可以使用集合 (O(1(( 代替
const removeDup = function(sll) {
const dupes = new Set()
let cur = { next: null }
// you can also as you suggested initialize cur as sll
// in which case you must mark it as "consumed" idem add the value to dupes
let sllIter = sll
while (sllIter) {
if (dupes.has(sllIter.value)) {
// early continue to avoid nesting else
// subjective preference
sllIter = sllIter.next
continue
}
dupes.add(sllIter.value)
// link our node to the currently being iterated node
cur.next = sllIter;
// advance our node
cur = sllIter
// advance iter
sllIter = sllIter.next
}
return sll
}
const l = (value, next) => ({ value, next })
const sllStr = ({ value: a, next: b }) => b ? `${a} -> ${sllStr(b)}`: a
const sll = l(1, l(1, l(2, l(1, l(2, l(3))))))
console.log(sllStr(removeDup(sll))) // 1 -> 2 -> 3
也许你可以写一个微型链表库。这是一个带有函数描述的功能;
toList
:获取数组将其转换为列表foldList
:类似减少的东西。获取列表、函数和累加器。sum
:获取一个列表并给出其总和:)prt
:漂亮打印列表nub
:从列表中删除重复。
function List(e){
this.data = e;
this.next = null;
}
List.fromArray = function([a,...as]){
var h = new List(a),
t = as.reduce((l,e) => [l[0],l[1].next = new List(e)], [h,h]);
return t[0];
};
List.prototype.fold = function (f,a){
var newa = f(a, this.data);
return this.next ? this.next.fold(f, newa)
: newa
};
List.prototype.log = function(){
return this.fold((a,e) => a + e + " -> ", "") + "null";
};
List.prototype.nub = function(){
var o = this.fold((a,e) => (a[e] = e, a), {}),
a = Object.values(o);
return List.fromArray(a);
}
var arr = [1, 1, 1, 1, 4, 10, 10, 3, 10, 9, 5, 5, 5, 8],
lst = List.fromArray(arr),
sum = l => l.fold((a,e) => a + e, 0), // just for fun
res = lst.nub().log();
console.log(res);
nub
是 O(n(。