Coderust: Hacking the Coding Interview/

...

/

Remove Duplicates from a Linked List

Remove Duplicates from a Linked List

Remove duplicate nodes from a linked list of integers, retaining only the first occurrence of each duplicate.

We'll cover the following...

Statement

Given a linked list of integers, remove all the duplicate nodes from the linked list while retaining only the first occurrence of each duplicate.

Example

The following example elaborates this further. The linked list, before we remove duplicates:

g head head a 4 head->a NULL NULL b 7 a->b c 4 b->c d 9 c->d e 7 d->e f 11 e->f g 4 f->g g->NULL

The linked list after we remove duplicates:

g head head a 4 head->a NULL NULL b 7 a->b d 9 b->d f 11 d->f f->NULL

Sample input

[4, 7, 4, 9, 7, 11, 4]

Expected output

[4, 7, 9, 11]

Try it yourself #

main.cpp
LinkedList.cpp
LinkedListNode.cpp
#include "LinkedList.cpp"
using namespace std;
LinkedListNode* RemoveDuplicates(LinkedListNode* head) {
	//TODO: Write - Your - Code
	return head;
}

Solution

Here is the pseudo-code of the algorithm that we are going to use. We iterate through the entire linked list and compare each node data with the hashset. Duplicate nodes are deleted as we iterate through the list.

n = length of linked list
add data of the first node to a hashset

for 2nd to the nth node in the linked list
  if data of 'node' is found in the hashset
    delete current node
  else
    add data of current node to the hashset
...