Remove Duplicates from a Sorted Linked List

Remove Duplicates from a Sorted Linked List
Problem Statement

Given a sorted singly linked list, remove duplicate nodes so that each element appears only once.

The linked list is already sorted, so duplicate values will be adjacent.

Example
Input: 2 -> 2 -> 4 -> 5
Output: 2 -> 4 -> 5

Input: 2 -> 2 -> 2 -> 2
Output: 2
Key Observation

Since the linked list is sorted:

Duplicate elements will always be next to each other
So we just need to compare current node with next node

This allows us to solve the problem in O(n) time and O(1) space.

Approach: Traverse and Remove Duplicates
Idea
Start from head
Compare current node with next node
If both values are same → remove next node
Else → move to next node
Continue until end
Step-by-Step Algorithm
Set current = head
While current and current.next exist:
If current.data == current.next.data
Remove next node → current.next = current.next.next
Else
Move current forward
Return head
Python Code
class Node:
def init(self, data):
self.data = data
self.next = None

def removeDuplicates(head):
current = head

while current and current.next:
    if current.data == current.next.data:
        current.next = current.next.next
    else:
        current = current.next

return head

def printList(head):
temp = head
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print("None")

Create Linked List: 2 -> 2 -> 4 -> 5

head = Node(2)
head.next = Node(2)
head.next.next = Node(4)
head.next.next.next = Node(5)

head = removeDuplicates(head)
printList(head)
Example Walkthrough
List: 2 -> 2 -> 4 -> 5

Compare 2 and 2 → Duplicate → Remove
List becomes: 2 -> 4 -> 5
Complexity Analysis
Type Complexity
Time O(n)
Space O(1)

This meets the expected complexity.

Summary Table
Step Action
Compare current and next Check duplicate
If duplicate Remove next node
Else Move forward
Continue Until end

Conclusion

To remove duplicates from a sorted linked list:

Since list is sorted, duplicates are adjacent
Compare current node with next node
Remove duplicate by changing pointer
No extra space required
Time complexity O(n)

This is a very common Linked List pointer manipulation problem.