Given an unsorted Linked List, the task is to remove duplicates from the list.
Examples:
Input: linked_list = 12 -> 11 -> 12 -> 21 -> 41 -> 43 -> 21
Output: 12 -> 11 -> 21 -> 41 -> 43
Explanation: Second occurrence of 12 and 21 are removed.
Input: linked_list = 12 -> 11 -> 12 -> 21 -> 41 -> 43 -> 21
Output: 12 -> 11 -> 21 -> 41 -> 43
Naive Approach to Remove Duplicates from an Unsorted Linked List:
The most simple approach to solve this, is to check each node for duplicate in the Linked List one by one.
Below is the Implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* newNode( int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
void removeDuplicates( struct Node* start)
{
struct Node *ptr1, *ptr2, *dup;
ptr1 = start;
while (ptr1 != NULL && ptr1->next != NULL) {
ptr2 = ptr1;
while (ptr2->next != NULL) {
if (ptr1->data == ptr2->next->data) {
dup = ptr2->next;
ptr2->next = ptr2->next->next;
delete (dup);
}
else
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}
void printList( struct Node* node)
{
while (node != NULL) {
printf ( "%d " , node->data);
node = node->next;
}
}
int main()
{
struct Node* start = newNode(10);
start->next = newNode(12);
start->next->next = newNode(11);
start->next->next->next = newNode(11);
start->next->next->next->next = newNode(12);
start->next->next->next->next->next = newNode(11);
start->next->next->next->next->next->next = newNode(10);
printf ( "Linked list before removing duplicates " );
printList(start);
removeDuplicates(start);
printf ( "\nLinked list after removing duplicates " );
printList(start);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* newNode( int data)
{
Node* temp = (Node*) malloc ( sizeof (Node));
temp->data = data;
temp->next = NULL;
return temp;
}
void removeDuplicates(Node* start)
{
Node *ptr1, *ptr2, *dup;
ptr1 = start;
while (ptr1 != NULL && ptr1->next != NULL) {
ptr2 = ptr1;
while (ptr2->next != NULL) {
if (ptr1->data == ptr2->next->data) {
dup = ptr2->next;
ptr2->next = ptr2->next->next;
free (dup);
}
else
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}
void printList( struct Node* node)
{
while (node != NULL) {
printf ( "%d " , node->data);
node = node->next;
}
}
int main()
{
struct Node* start = newNode(10);
start->next = newNode(12);
start->next->next = newNode(11);
start->next->next->next = newNode(11);
start->next->next->next->next = newNode(12);
start->next->next->next->next->next = newNode(11);
start->next->next->next->next->next->next = newNode(10);
printf ( "Linked list before removing duplicates " );
printList(start);
removeDuplicates(start);
printf ( "\nLinked list after removing duplicates " );
printList(start);
return 0;
}
|
Java
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node( int d)
{
data = d;
next = null ;
}
}
void remove_duplicates()
{
Node ptr1 = null , ptr2 = null , dup = null ;
ptr1 = head;
while (ptr1 != null && ptr1.next != null ) {
ptr2 = ptr1;
while (ptr2.next != null ) {
if (ptr1.data == ptr2.next.data) {
ptr2.next = ptr2.next.next;
System.gc();
}
else {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
void printList(Node node)
{
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node( 10 );
list.head.next = new Node( 12 );
list.head.next.next = new Node( 11 );
list.head.next.next.next = new Node( 11 );
list.head.next.next.next.next = new Node( 12 );
list.head.next.next.next.next.next = new Node( 11 );
list.head.next.next.next.next.next.next
= new Node( 10 );
System.out.println(
"Linked List before removing duplicates : " );
list.printList(head);
list.remove_duplicates();
System.out.println( "\n" );
System.out.println(
"Linked List after removing duplicates : " );
list.printList(head);
}
}
|
Python3
class Node():
def __init__( self , data):
self .data = data
self . next = None
class LinkedList():
def __init__( self ):
self .head = None
def remove_duplicates( self ):
ptr1 = None
ptr2 = None
dup = None
ptr1 = self .head
while (ptr1 ! = None and ptr1. next ! = None ):
ptr2 = ptr1
while (ptr2. next ! = None ):
if (ptr1.data = = ptr2. next .data):
dup = ptr2. next
ptr2. next = ptr2. next . next
else :
ptr2 = ptr2. next
ptr1 = ptr1. next
def printList( self ):
temp = self .head
while (temp ! = None ):
print (temp.data, end = " " )
temp = temp. next
print ()
list = LinkedList()
list .head = Node( 10 )
list .head. next = Node( 12 )
list .head. next . next = Node( 11 )
list .head. next . next . next = Node( 11 )
list .head. next . next . next . next = Node( 12 )
list .head. next . next . next . next . next = Node( 11 )
list .head. next . next . next . next . next . next = Node( 10 )
print ( "Linked List before removing duplicates :" )
list .printList()
list .remove_duplicates()
print ()
print ( "Linked List after removing duplicates :" )
list .printList()
|
C#
using System;
class List_ {
Node head;
class Node {
public int data;
public Node next;
public
Node( int d)
{
data = d;
next = null ;
}
}
void remove_duplicates()
{
Node ptr1 = null , ptr2 = null ;
ptr1 = head;
while (ptr1 != null && ptr1.next != null ) {
ptr2 = ptr1;
while (ptr2.next != null ) {
if (ptr1.data == ptr2.next.data) {
ptr2.next = ptr2.next.next;
}
else
{
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
void printList(Node node)
{
while (node != null ) {
Console.Write(node.data + " " );
node = node.next;
}
}
public static void Main(String[] args)
{
List_ list = new List_();
list.head = new Node(10);
list.head.next = new Node(12);
list.head.next.next = new Node(11);
list.head.next.next.next = new Node(11);
list.head.next.next.next.next = new Node(12);
list.head.next.next.next.next.next = new Node(11);
list.head.next.next.next.next.next.next
= new Node(10);
Console.WriteLine(
"Linked List_ before removing duplicates: " );
list.printList(list.head);
list.remove_duplicates();
Console.WriteLine( "" );
Console.WriteLine(
"Linked List_ after removing duplicates: " );
list.printList(list.head);
}
}
|
Javascript
<script>
var head;
class Node {
constructor(val) {
this .data = val;
this .next = null ;
}
}
function remove_duplicates() {
var ptr1 = null , ptr2 = null , dup = null ;
ptr1 = head;
while (ptr1 != null && ptr1.next != null ) {
ptr2 = ptr1;
while (ptr2.next != null ) {
if (ptr1.data == ptr2.next.data) {
dup = ptr2.next;
ptr2.next = ptr2.next.next;
} else {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
function printList( node) {
while (node != null ) {
console.log(node.data + " " );
node = node.next;
}
}
head = new Node(10);
head.next = new Node(12);
head.next.next = new Node(11);
head.next.next.next = new Node(11);
head.next.next.next.next = new Node(12);
head.next.next.next.next.next = new Node(11);
head.next.next.next.next.next.next = new Node(10);
document.write( "Linked List before removing duplicates : <br/> " );
printList(head);
remove_duplicates();
document.write( "<br/>" );
document.write( "Linked List after removing duplicates : <br/> " );
printList(head);
</script>
|
Output
Linked list before removing duplicates 10 12 11 11 12 11 10
Linked list after removing duplicates 10 12 11
Time Complexity: O(N2)
Auxiliary Space: O(1)
Remove duplicates from an Unsorted Linked List using Hashing:
The idea for this approach is based on the following observations:
- Traverse the link list from head to end.
- For every newly encountered element, check whether if it is in the hash table:
- if yes, remove it
- otherwise put it in the hash table.
- At the end, the Hash table will contain only the unique elements.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* newNode( int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
void removeDuplicates( struct Node* start)
{
unordered_set< int > seen;
struct Node* curr = start;
struct Node* prev = NULL;
while (curr != NULL) {
if (seen.find(curr->data) != seen.end()) {
prev->next = curr->next;
delete (curr);
}
else {
seen.insert(curr->data);
prev = curr;
}
curr = prev->next;
}
}
void printList( struct Node* node)
{
while (node != NULL) {
printf ( "%d " , node->data);
node = node->next;
}
}
int main()
{
struct Node* start = newNode(10);
start->next = newNode(12);
start->next->next = newNode(11);
start->next->next->next = newNode(11);
start->next->next->next->next = newNode(12);
start->next->next->next->next->next = newNode(11);
start->next->next->next->next->next->next = newNode(10);
printf ( "Linked list before removing duplicates : \n" );
printList(start);
removeDuplicates(start);
printf ( "\nLinked list after removing duplicates : \n" );
printList(start);
return 0;
}
|
Java
import java.util.HashSet;
public class removeDuplicates {
static class node {
int val;
node next;
public node( int val) { this .val = val; }
}
static void removeDuplicate(node head)
{
HashSet<Integer> hs = new HashSet<>();
node current = head;
node prev = null ;
while (current != null ) {
int curval = current.val;
if (hs.contains(curval)) {
prev.next = current.next;
}
else {
hs.add(curval);
prev = current;
}
current = current.next;
}
}
static void printList(node head)
{
while (head != null ) {
System.out.print(head.val + " " );
head = head.next;
}
}
public static void main(String[] args)
{
node start = new node( 10 );
start.next = new node( 12 );
start.next.next = new node( 11 );
start.next.next.next = new node( 11 );
start.next.next.next.next = new node( 12 );
start.next.next.next.next.next = new node( 11 );
start.next.next.next.next.next.next = new node( 10 );
System.out.println(
"Linked list before removing duplicates :" );
printList(start);
removeDuplicate(start);
System.out.println(
"\nLinked list after removing duplicates :" );
printList(start);
}
}
|
Python3
class Node:
def __init__( self , data):
self .data = data
self . next = None
class LinkedList:
def __init__( self ):
self .head = None
def printlist( self ):
temp = self .head
while (temp):
print (temp.data, end = " " )
temp = temp. next
def removeDuplicates( self , head):
if self .head is None or self .head. next is None :
return head
hash = set ()
current = head
hash .add( self .head.data)
while current. next is not None :
if current. next .data in hash :
current. next = current. next . next
else :
hash .add(current. next .data)
current = current. next
return head
if __name__ = = "__main__" :
llist = LinkedList()
llist.head = Node( 10 )
second = Node( 12 )
third = Node( 11 )
fourth = Node( 11 )
fifth = Node( 12 )
sixth = Node( 11 )
seventh = Node( 10 )
llist.head. next = second
second. next = third
third. next = fourth
fourth. next = fifth
fifth. next = sixth
sixth. next = seventh
print ( "Linked List before removing Duplicates." )
llist.printlist()
llist.removeDuplicates(llist.head)
print ( "\nLinked List after removing duplicates." )
llist.printlist()
|
C#
using System;
using System.Collections.Generic;
class removeDuplicates {
class node {
public int val;
public node next;
public node( int val) { this .val = val; }
}
static void removeDuplicate(node head)
{
HashSet< int > hs = new HashSet< int >();
node current = head;
node prev = null ;
while (current != null ) {
int curval = current.val;
if (hs.Contains(curval)) {
prev.next = current.next;
}
else {
hs.Add(curval);
prev = current;
}
current = current.next;
}
}
static void printList(node head)
{
while (head != null ) {
Console.Write(head.val + " " );
head = head.next;
}
}
public static void Main(String[] args)
{
node start = new node(10);
start.next = new node(12);
start.next.next = new node(11);
start.next.next.next = new node(11);
start.next.next.next.next = new node(12);
start.next.next.next.next.next = new node(11);
start.next.next.next.next.next.next = new node(10);
Console.WriteLine( "Linked list before removing "
+ "duplicates :" );
printList(start);
removeDuplicate(start);
Console.WriteLine( "\nLinked list after removing "
+ "duplicates :" );
printList(start);
}
}
|
Javascript
class node {
constructor(val) {
this .val = val;
this .next = null ;
}
}
function removeDuplicate( head) {
var hs = new Set();
var current = head;
var prev = null ;
while (current != null ) {
var curval = current.val;
if (hs.has(curval)) {
prev.next = current.next;
} else {
hs.add(curval);
prev = current;
}
current = current.next;
}
}
function printList( head) {
while (head != null ) {
console.log(head.val + " " );
head = head.next;
}
}
start = new node(10);
start.next = new node(12);
start.next.next = new node(11);
start.next.next.next = new node(11);
start.next.next.next.next = new node(12);
start.next.next.next.next.next = new node(11);
start.next.next.next.next.next.next = new node(10);
console.log(
"Linked list before removing duplicates :<br/>"
);
printList(start);
removeDuplicate(start);
console.log(
"<br/>Linked list after removing duplicates :<br/>"
);
printList(start);
|
Output
Linked list before removing duplicates :
10 12 11 11 12 11 10
Linked list after removing duplicates :
10 12 11
Time Complexity: O(N), on average (assuming that hash table access time is O(1) on average).
Auxiliary Space: O(N), As extra space is used to store the elements in the stack.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!