## Introduction

In this blog, we will learn how we can **remove duplicates from linked list. **So let's suppose we have a Linked List sorted in increasing order, and it may or may not contain some duplicate nodes. Now we need to remove all the duplicate nodes from this link list. **For example-**

There are numerous approaches to doing the above task, as we can travel through the linked list by comparing the current node with its next node and removing the next node if it is equal. Or we can also use a two-pointer approach where the first pointer helps us traverse through the linked list, and the second pointer only points to the distinct nodes in the list. Another approach could be to use an unordered map to store all the nodes, and as maps don't allow duplicates, thus we will get rid of all the duplicates. So let's see all of these methods one by one; start with the simple traversal-based approach.

**Recommended:** *Before stepping on to the solution, try it by yourself on Coding Ninjas Studio.*

Here are the list of approaches to remove duplicates from linked list are as follows:

- Naive Approach
- Using Two Pointers Approach
- Using Maps Approach
- Using Set data structure

## Naive Approach

The naive approach to solve this problem 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. Finally, print the linked list. This approach can be implemented using recursion, so let's go through both implementations one by one.

### Algorithm

- Take the linked list from user input-
- Iterate through the linked list and compare the current node with the next node-
- If they are equal, delete the next node after storing the pointer to the next node of the next node. Then link the current node with the next to the next node.
- If not, then continue traversing the linked list.
- Finally, print the linked list.

### Implementation in C++

**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)**, where N is the number of nodes in the linked list.

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

### Recursive Implementation of Naive Approach

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(N)**

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

**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)