删除javascript链表的重复项

Question

这是我目前为止比较节点的代码:

const removeDuplicates = (headNode) => { 
let cur = headNode;
while (cur.next) {
let nextnode = cur.next;
if (cur.data == nextnode.data) {
cur.next = cur.next.next;
} else {
cur = cur.next;    
}
}
return headNode;
}

如果列表为[1, 2, 1, 3, 4, 2, 1]=>[1, 2, 3, 4]

第四个节点应该是4，但得到的却是1，为什么?
如何解决这个问题?

Answer 1

当前您正在检查2个相邻节点，如果这2个相邻节点彼此不相等，则会错过其他节点，例如[1, 2, 1, 2, 1]

一个解决方案是用一个集合来检查数据是否被访问过

const removeDuplicates = (headNode) => {
let cur = headNode;
let visited = new Set([cur.data]);
while (cur.next) {
let nextnode = cur.next;
if (visited.has(nextnode.data)) {
// if current node data is visited, skip
cur.next = nextnode.next;
} else {
// if current node data is not visited, visit
visited.add(nextnode.data);
cur = nextnode;
}
}
return headNode;
};

class Node {
constructor(data = null) {
this.data = data;
this.next = null;
}
}
const removeDuplicates = (headNode) => {
let cur = headNode;
let visited = new Set([cur.data]);
while (cur.next) {
let nextnode = cur.next;
if (visited.has(nextnode.data)) {
// if current node data is visited, skip
cur.next = nextnode.next;
} else {
// if current node data is not visited, visit
visited.add(nextnode.data);
cur = nextnode;
}
}
return headNode;
};
// prepare data
const arr = [1, 2, 1, 3, 4, 2, 1];
let head, prevNode;
while (arr.length > 0) {
let node = new Node(arr.pop());
if (prevNode) {
node.next = prevNode;
}
head = node;
prevNode = node;
}
// remove duplicate
const headAfterRemove = removeDuplicates(head);
// verify result
let cursor = headAfterRemove;
while (cursor) {
console.log(cursor.data);
cursor = cursor.next;
}