Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1
3.1.
Code
4.
Approach 2
4.1.
Algorithm
4.2.
Code
5.
Frequently Asked Questions
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.

Author Saksham Gupta
3 upvotes
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Linked List

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.

Linked List

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.

 

                   Linked List

 

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;

// Linked List Node Class.
class Node
{
public:
   int data;
   Node *next;

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

Node *uniqueSortedList(Node *head)
{
   // New head of the Linked List.
   Node *nhead = NULL;
   Node *tail = NULL;

   // Map to store the frequency.
   unordered_set<int> nodeSet;
   Node *temp = head;

   // 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)
       {
           if (nhead == NULL)
           {
               nhead = temp;
               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;
   }

   // Returning new head.
   return nhead;
}

// Function to print the Linked List.
void print(Node *head)
{
   Node *temp = head;
   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)
       {
           head = tail = newNode;
       }
       else
       {
           tail->next = newNode;
           tail = newNode;
       }
   }
   cout << "Unique sorted list: ";

   // Calling the function to delete duplicates.
   uniqueSortedList(head);

   // Printing the final list.
   print(head);
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

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.
  • Finally, we can return the ‘HEAD’ of the linked list.

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.
Node *uniqueSortedList(Node *head)
{
   // Initialize 'TEMP' to store head
   Node *temp = 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)
       {
           // Adjust links to remove the next element
           temp->next = temp->next->next;
       }

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

   return head;
}

// Printing the linked list.
void print(Node *head)
{
   Node *temp = head;
   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) {
           head = tail = newNode;
       }
       else {
           tail->next = newNode;
           tail = newNode;
       }
   }
   cout << "Unique sorted list: ";
   // Calling the function to delete duplicates.
   uniqueSortedList(head);

   // Printing the final list.
   print(head);
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

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

Frequently Asked Questions

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. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass