CODEWITHSUNDEEP
javascriptclasslinked-listduplicates
niconi
niconi

Reputation: 51

removing the duplicates of a linked list javascript

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 ?

Upvotes: 0

Views: 1549

Answers (1)

hgb123
hgb123

Reputation: 14891

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

Upvotes: 3

Related Questions