## 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!