1.
Introduction
2.
Problem Statement
3.
Approach 1
3.1.
Code
4.
Approach 2
4.1.
Algorithm
4.2.
Code
5.
5.1.
What is the time complexity of insertion in a Linked List?
5.2.
What is the time complexity for removing an element from a Linked List?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Remove Duplicates from a Sorted Linked List.

Saksham Gupta
1 upvote

## Introduction

Every tech interview is incomplete without a linked list. There is hardly any instance when the interviewee isnâ€™t asked about this favorite topic of interviewers. Thus practicing the questions on Linked List will surely give you an upper hand. Today we will see a such question which is regularly asked in interviews, i.e., remove duplicates from a sorted linked list. You can practice the problem here on Coding Ninjas Studio, and return to this blog if you feel stuck.

Also see, Data Structures

## Problem Statement

We have been given a sorted linked list, and we have to remove the duplicates from it, or we have to return a sorted linked list that contains only unique values.

Letâ€™s say that the linked list that is given to us is this.

Thus, we can see that 12 is occurring twice and 15 is occurring twice, so we have to remove one of their occurrences, and our final list would look like this.

Okay, but how will we solve this problem?

Letâ€™s look at the different approaches to solving this problem.

Recommended: Try the Problem yourself before moving on to the solution.

## Approach 1

We can use a HashSet to check whether a node has already been visited or not. We will create a new head variable and loop through the linked list, and check If the current node is visited. If yes, we can simply skip that node, and if itâ€™s not, we will add that node to our new linked list. Weâ€™ll insert the node in the hash set and move ahead.

Youâ€™ll get a picture of whatâ€™s happening through the code.

Below is the code for the above implementation.

### Code

``````#include <iostream>
#include <unordered_set>
using namespace std;

class Node
{
public:
int data;
Node *next;

Node(int data)
{
this->data = data;
this->next = NULL;
}
};

{
Node *tail = NULL;

// Map to store the frequency.
unordered_set<int> nodeSet;

// Looping over the list.
while (temp != NULL)
{
// If it is not visited, we will add it to our new list.
if (nodeSet.count(temp->data) == 0)
{
{
tail = temp;
}
else
{
tail->next = temp;
tail = tail->next;
}
}

// Inserting the current element in the hashset.
nodeSet.insert(temp->data);
temp = temp->next;
}

if (tail)
{
tail->next = NULL;
}

}

// Function to print the Linked List.
{
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}

int main()
{
int n;
cout << "Enter the number of elements in the list: ";
cin >> n;

cout << "Enter the elements: ";
Node *head = NULL, *tail = NULL;

for (int i = 0; i < n; i++)
{
int data;
cin >> data;
Node *newNode = new Node(data);
if (i == 0)
{
}
else
{
tail->next = newNode;
tail = newNode;
}
}
cout << "Unique sorted list: ";

// Calling the function to delete duplicates.

// Printing the final list.
return 0;
}``````

Input

``12 12 13 14 15 15``

Output

``12 13 14 15``

Time Complexity

O(L), where â€˜Lâ€™ represents the length of the linked list. As each element in the input list is traversed exactly once. Hence the time complexity is O( L ).

Space Complexity

The space complexity is O(L), where â€˜Lâ€™ represents the length of the linked list.

Because in the worst case the hash set can contain all the nodes of the linked list.

## Approach 2

We have been given a sorted list, and we can make use of it as the duplicates for a particular number will be adjacent to it; thus, we can check for a particular number if the next number is the same as itself. If it is the same, then we can simply point its next pointer to its next nodeâ€™s next pointer. You will get a better understanding of this from the algorithm below.

### Algorithm

• We will create a â€˜TEMPâ€™ pointer and initialize it to â€˜HEADâ€™ of the linked list given to us.
• Then we will loop through the linked list and check if the current (â€˜TEMPâ€™) element is equal to the next element. If it is, then we will set TEMP->NEXT = TEMP->NEXT->NEXT as discussed above. And if it is not equal, we will simply set TEMP = TEMP - > next.

Below is the code for the above implementation

### Code

``````#include <iostream>
using namespace std;

// Structure of a Node.
class Node
{
public:
int data;
Node *next;

Node (int data) {
this->data = data;
this->next = NULL;
}
};

// Function to delete duplicates.
{
// Initialize 'TEMP' to store head

// Run a while loop to loop through the linked list.
while (temp != NULL && temp->next != NULL)
{

// Next element has the same value as the current element
if (temp->next->data == temp->data)
{
temp->next = temp->next->next;
}

// Next element is different from the current element
else
{
temp = temp->next;
}
}

}

{
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}

int main()
{
int n;
cout << "Enter the number of elements in the list: ";
cin >> n;

cout << "Enter the elements: ";
Node *head = NULL,  *tail = NULL;

for (int i = 0; i < n; i++) {
int data;
cin >> data;
Node *newNode = new Node(data);
if (i == 0) {
}
else {
tail->next = newNode;
tail = newNode;
}
}
cout << "Unique sorted list: ";
// Calling the function to delete duplicates.

// Printing the final list.
return 0;
}``````

Input

``````Enter the number of elements in the list: 6
Enter the elements: 12 12 13 14 15 15``````

Output

``Unique sorted list: 12 13 14 15``

Time Complexity

O(L), where â€˜Lâ€™ represents the length of the linked list. As each element in the input list, is traversed exactly once, the links are adjusted accordingly to remove duplicates. Hence the time complexity is O(L).

Space Complexity

O(1). As no extra space is used.

Check out this problem - Duplicate Subtree In Binary Tree

### What is the time complexity of insertion in a Linked List?

The time complexity is O(N) as one has to reach the end of the linked list to add a new node

### What is the time complexity for removing an element from a Linked List?

The time complexity is O(N) which is mainly due to the searching part in the algorithm as we heave to traverse through the linked list in its entirety to search for an element and the deletion part takes a constant O(1) time

## Conclusion

We saw two different methods to solve the problem, â€˜remove duplicates from a sorted linked listâ€™. We saw how we could first use HashSet and then save the space complexity by omitting them. Now, after learning this new problem, you must be feeling confident on the topic of Linked Lists, but this is just the beginning, and you still have a lot to learn. But don't worry, we have a solution for that too. Move over to our industry-leading practice platform Coding Ninjas Studio to practice top problems, read interview experiences, and much more.