破解编码面试2.1 去除单链表中的重复值javascript

Question

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

有人可以解释为什么下面的 'solution' 会导致无限循环吗？

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 个副本的链表，但我不明白为什么它会产生无限循环。或者，如果有人能指出我正确的调试方向，那也将不胜感激！

Answer 1

看起来您最终定义了一个在您的 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);
 }
}

Answer 2

如何调查您的错误

可以使用调试器，不过像我这种原始人，也可以使用console.log

万一死循环，你要的就是挣脱

let count = 0
while (pointer && count++<5) {
  //whatever
}

即使您的算法失败，您仍然会退出

输出你的变量

发挥创意并在您认为合适的地方发送垃圾邮件console.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) look

您可以改用集合 (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

Answer 3

你也许可以写一个微型链表库。这是一个带有功能描述的；

toList : 将数组转换为列表
foldList : 类似 reduce 的东西。接受一个列表、一个函数和一个累加器。
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)。

破解编码面试2.1 去除单链表中的重复值javascript

Cracking the coding interview 2.1 remove duplicate values from singly linked list javascript

javascript

algorithm

infinite-loop

singly-linked-list