This is my code so far comparing the nodes to each other:
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;
}
If the list is [1, 2, 1, 3, 4, 2, 1] => [1, 2, 3, 4]
The fourth node should be 4 but instead get 1, why?
How can I fix this ?
Currently you are checking the 2 adjacent nodes, it will miss other if those 2 adjacent nodes is not equal to each other, like the case [1, 2, 1, 2, 1]
One solution is to have a set that check if the data has been visited
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;
}
Setobject to remove duplicates from an array, e.g.console.log([...new Set(arr)]);