## Using Two Pointers Approach

This approach uses two-pointers to remove duplicates from the sorted linked list. The first pointer iterates through the whole list. And the second pointer moves over only those nodes which are distinct. While iterating through the list, whenever the first pointer encounter duplicate nodes, it skips them, and when it encounters a distinct node, it moves the second pointer from the last distinct node to this new node.

### Algorithm

- Take the linked list from user input-
- Declare two-pointers and initialize them with the head of the linked list
- Iterate through the list using the first pointer-
- If it encounters a node that duplicates its previous, it does nothing, and if the node is distinct, it moves the second pointer to that node.
- Print the linked list.

### Implementation in C++

### C++

`#include <bits/stdc++.h>`

using namespace std;

//Structure for a node in linked list.

struct node

{

int data;

struct node *next;

};

//Function to remove duplicates.

void removeduplicates(node* head)

{

//Two reference pointers, one for iterating through the linked

//list, another for pointing to first occurence of every

//distinct node.

node *ptr1 =head;

node *ptr2=head;

//Traversing through the list.

while(ptr1!=nullptr)

{

//Comparing the current node with the next node.

if(ptr1->data!=ptr2->data)

{

//If a new node is found, skip the duplicates.

ptr2->next=ptr1;

ptr2=ptr1;

}

//Move the iterator to the next node.

ptr1=ptr1->next;

}

//When the last node has duplicates.

if(ptr2!=ptr1)

{

ptr2->next=nullptr;

}

}

//Function to push nodes into the list.

void push(struct node** headr, int new_val)

{

//Creatng a new node.

struct node* new_node= new node();

//Putting the value in the node.

new_node->data= new_val;

//Linking the node to the list.

new_node->next=(*headr);

//Shifting the head pointer to the new node.

*headr= new_node;

}

//Driver function.

int main()

{

//Creating an empty list.

struct node* head=nullptr;

//Enter no of nodes in the node.

int size;

cout<<"Enter the number of nodes in the list- ";

cin>>size;

//Pushing the nodes in it.

cout<<"Enter the nodes in the list- ";

for(int i=0;i<size;i++)

{

int a;

cin>>a;

push(&head,a);

}

//To remove duplicates from the sorted linked list.

removeduplicates(head);

//Printing the linked list.

while(head!=nullptr)

{

cout<<head->data<<" ";

head=head->next;

}

return 0;

}

**Input**

```
7
5 4 3 2 2 2 1
```

**Output**

```
Enter the number of nodes in the list-
Enter the nodes in the list-
1 2 3 4 5
```

### Complexity Analysis

The **time complexity **of this approach is- O(N)

The **space complexity** of this approach is- O(1)

## Using Maps Approach

Another approach to solving this problem is using maps. We traverse through the linked list and check if the node has already occurred or node. If it has not occurred, we print it and mark it as visited on the map. And skip it if it is already visited.

### Algorithm

- Take the linked list from user input-
- Create a map that takes node data and boolean variables as key-value pairs.
- Traverse through the linked list, and if a node appears for the first time or not-
- If Yes, print it and mark it as visited on the map.
- Else move on to the next node.

### Implementation in C++

### C++

`#include <bits/stdc++.h>`

using namespace std;

//Structure for a node in the linked list.

struct node

{

int data;

struct node *next;

};

//Function to remove duplicates.

void removeduplicates(node* head)

{

//Map to store the distinct values.

unordered_map<int, bool> distinctnodes;

//To traverse through the nodes.

node* curr=head;

while(curr)

{

//If the current nodes is its first occurence.

if(distinctnodes.find(curr->data)==distinctnodes.end())

{

cout<<curr->data<<" ";

}

//Marked the node as visited.

distinctnodes[curr->data]=true;

curr=curr->next;

}

}

//Function to push nodes into the list.

void push(struct node** headr, int new_val)

{

//Creatng a new node.

struct node* new_node= new node();

//Putting the value in the node.

new_node->data= new_val;

//Linking the node to the list.

new_node->next=(*headr);

//Shifting the head pointer to the new node.

*headr= new_node;

}

//Driver function.

int main()

{

//Creating an empty list.

struct node* head=nullptr;

//Enter no of nodes in the node.

int size;

cout<<"Enter the number of nodes in the list- ";

cin>>size;

//Pushing the nodes in it.

cout<<"Enter the nodes in the list- ";

for(int i=0;i<size;i++)

{

int a;

cin>>a;

push(&head,a);

}

//To remove duplicates from the sorted linked list.

removeduplicates(head);

}

**Input**

```
7
5 4 3 2 2 2 1
```

**Output**

```
Enter the number of nodes in the list-
Enter the nodes in the list-
1 2 3 4 5
```

### Complexity Analysis

The **time complexity** of this approach is-** O(N)**

The **space complexity** of this approach is- **O(1)**

**Using Set data structure**

Using a set data structure is an efficient approach for removing duplicates from a linked list. Sets in C++ (and similarly in other languages) provide constant time complexity for insertion and lookup operations, making them ideal for this task. By iterating through the linked list and maintaining a set of unique values encountered so far, we can easily identify and remove duplicates.

**Algorithm**

- Traverse the linked list.
- For each node, check if its value already exists in the set.
- If it does not exist, add its value to the set and continue to the next node.
- If it does exist, remove the node from the linked list.
- Continue until the end of the linked list is reached.

**Implementation in C++**

### C++

`#include <iostream>`

#include <unordered_set>

using namespace std;

struct ListNode {

int val;

ListNode *next;

ListNode(int x) : val(x), next(nullptr) {}

};

ListNode* removeDuplicates(ListNode* head) {

if (!head) return nullptr;

unordered_set<int> seen;

ListNode *current = head;

ListNode *prev = nullptr;

while (current) {

if (seen.find(current->val) == seen.end()) {

seen.insert(current->val);

prev = current;

} else {

prev->next = current->next;

delete current;

}

current = prev->next;

}

return head;

}

void printList(ListNode* head) {

ListNode* temp = head;

while (temp != nullptr) {

cout << temp->val << " ";

temp = temp->next;

}

cout << endl;

}

int main() {

ListNode* head = new ListNode(1);

head->next = new ListNode(2);

head->next->next = new ListNode(3);

head->next->next->next = new ListNode(2);

head->next->next->next->next = new ListNode(4);

cout << "Original List: ";

printList(head);

head = removeDuplicates(head);

cout << "List after removing duplicates: ";

printList(head);

return 0;

}

**Output**

```
Original List: 1 2 3 2 4
List after removing duplicates: 1 2 3 4
```

**Complexity Analysis**

**Time complexity:** O(n), where n is the number of nodes in the linked list. This is because we traverse the entire linked list once.**Space complexity: **O(n), where n is the number of unique elements in the linked list. This is because we store unique elements in a set.

## Frequently Asked Questions

**What are the types of the linked list?**

The linked list is generally of four types-

- Singly-linked list

- Doubly linked list

- Circular linked list

- Doubly circular linked list

**How do you remove duplicates from a linked list?**

Duplicates can be removed by using two pointers approach. The first pointer iterates through the whole list. And the second pointer moves over only those nodes which are distinct. While iterating through the list, whenever the first pointer encounter duplicate nodes, it skips them.

**How to remove duplicate values in linked list in C?**

Duplicates can be removed by a naive approach. The naive approach is to iterate through the linked list and keep comparing the current node with its next node, and if they are the same, delete the next node and move to the next node.

**How do you remove duplicates from LinkedList in Java?**

A set does not have duplicate elements in the Collection structure. We will use LinkedHashSet because it will maintain the order in the same way as LinkedList does since we are aware of this. By transforming the linked list into a linked hash set, we will eliminate duplicates from it.

**How do I remove duplicates in doubly linked list?**

By utilising a basic technique, duplicates in a doubly linked list can be eliminated. Two loops are utilized in this manner, which is the simplest. The inner loop compares the selected element with the other elements after the outer loop picks each element one at a time.

## Conclusion

In this blog, we learned the different approaches used to **remove duplicates from the sorted linked list.**

- We started with the basic approach of
**traversing through the linked list** and comparing the current node with the next node, and if they are equal, delete the next node and link the current node to the next node. - The second approach used
**two pointers**. One iterates through the whole list, and the second pointer moves only over the distinct nodes. In this method, the first pointer continues traversing until it finds a distinct node, and then the second pointer is moved to that node. Finally, we print the nodes traversed by the second pointer. - The last approach uses a map to remove duplicates from the sorted linked list. We create a
**map** with integer and bool as key-value pairs. Now we traverse through the linked list and check if a node is visited or not. If not, we print it, and if visited, we continue the traversal without printing.

More suggested problems based on LinkedList are Remove Duplicates from Sorted List, Add One to LinkedList, Cycle Detection in Singly LinkedList, and many more.

Refer to the top list of problems of Map data structure.

I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the Coding Ninjas Studio. Enroll in our courses, refer to the test series and problems available, and look at the interview bundle for placement preparations for big tech companies like Amazon, Microsoft, Google, and many more.

Do upvote our blogs if you find them helpful and engaging!

**Happy Learning!!**