Posted on by Kalkicode

# Remove duplicates from a sorted linked list

The problem at hand is to remove duplicate nodes from a sorted singly linked list. This entails eliminating nodes with duplicate values, such that the resulting linked list contains only unique values in ascending order.

## Problem Description

Given a sorted singly linked list, we need to modify it in such a way that all duplicate elements are removed, and only distinct elements are retained. The relative order of the unique elements should be preserved.

## Example

Consider the following sorted linked list:

``1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 -> 6 -> 7``

After removing duplicates, the modified linked list should be:

``1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7``

## Idea to Solve the Problem

To solve this problem, we can iterate through the linked list while maintaining two pointers - one pointing to the current node and another to the next node. If the current node's value is equal to the next node's value, we skip the next node by adjusting pointers. If they are not equal, we move both pointers ahead. This way, we can effectively remove duplicates while updating the linked list's structure.

## Pseudocode

``````deleteDuplicates(linkedList):
return

while current is not NULL:
nextNode = current.next
while nextNode is not NULL and current.data = nextNode.data:
nextNode = nextNode.next

current.next = nextNode
current = nextNode``````

## Algorithm Explanation

1. Start with the `current` pointer pointing to the head of the linked list.
2. Traverse through the linked list using the `current` pointer: a. Initialize a `nextNode` pointer to the node next to the `current` node. b. Check if `nextNode` exists and has the same value as the `current` node. If yes, move the `nextNode` pointer to the next node with a different value. c. Update the `current` node's `next` pointer to point to the `nextNode`. d. Update the `current` pointer to the `nextNode`.
3. Repeat step 2 until the `current` pointer reaches the end of the linked list.
4. The linked list will now be free of duplicate nodes.

## Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. This is because we are iterating through each node once and removing duplicates in a linear manner.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post