Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Remove Duplicates from a Linked List

Explore methods to remove duplicates from a linked list while keeping the first occurrence. Understand how to use hash sets for linear time removal and learn space-optimized alternatives without extra memory. This lesson prepares you to handle duplicate removal scenarios with different constraints efficiently.

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

Files
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
...