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):
if linkedList.head is NULL:
return
current = linkedList.head
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
- Start with the
current
pointer pointing to the head of the linked list. - Traverse through the linked list using the
current
pointer: a. Initialize anextNode
pointer to the node next to thecurrent
node. b. Check ifnextNode
exists and has the same value as thecurrent
node. If yes, move thenextNode
pointer to the next node with a different value. c. Update thecurrent
node'snext
pointer to point to thenextNode
. d. Update thecurrent
pointer to thenextNode
. - Repeat step 2 until the
current
pointer reaches the end of the linked list. - The linked list will now be free of duplicate nodes.
Code Solution
-
1) Delete duplicate nodes from sorted linked list in c
2) Delete duplicate nodes from sorted linked list in java
3) Delete duplicate nodes from sorted linked list in c++
4) Delete duplicate nodes from sorted linked list in c#
5) Delete duplicate nodes from sorted linked list in go
6) Delete duplicate nodes from sorted linked list in php
7) Delete duplicate nodes from sorted linked list in ruby
8) Delete duplicate nodes from sorted linked list in kotlin
9) Delete duplicate nodes from sorted linked list in swift
10) Delete duplicate nodes from sorted linked list in scala
11) Delete duplicate nodes from sorted linked list in python
12) Delete duplicate nodes from sorted linked list in js
13) Remove existing duplicate node of sorted linked list in typescript
14) Remove existing duplicate node of sorted list linked in vb.net
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.
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.
New Comment