Remove Duplicates from a Sorted Linked List

Linked lists are a fundamental data structure in computer science. One common problem is removing duplicates from a sorted linked list. Since the list is sorted, any duplicates will appear consecutively, which makes the task straightforward and efficient.

Problem Statement

Given a singly linked list, remove all duplicate nodes so that only the first occurrence of each value remains.

Examples:

Input:
2 -> 2 -> 4 -> 5

Output:
2 -> 4 -> 5

Input:
2 -> 2 -> 2 -> 2 -> 2

Output:
2

Constraints:

Number of nodes: 1 ≤ n ≤ 10^5
Node values: 1 ≤ data ≤ 10^5
Expected time complexity: O(n)
Expected space complexity: O(1)

Approach

Since the linked list is sorted, duplicates will always be adjacent. This allows us to remove duplicates in-place:

Start from the head node.
Compare the current node with the next node.
If they are equal, skip the next node by updating current.next.
Otherwise, move to the next node.
Repeat until the end of the list.

No extra space is required, making the algorithm space-efficient.

Python Code

def removeDuplicates(head):
current = head
while current and current.next:
if current.data == current.next.data:
current.next = current.next.next # skip duplicate
else:
current = current.next
return head

Explanation

We use a pointer current to traverse the linked list.
For each node, we check if its data is equal to the data of the next node.
If yes, we skip the next node by pointing current.next to current.next.next.
Otherwise, we move current forward.
This ensures all duplicates are removed in one pass.

Key Points

Works only for sorted linked lists.
Time Complexity: O(n) — each node is visited once.
Space Complexity: O(1) — no extra memory is used.
Simple, clean, and efficient — ideal for coding interviews and competitive programming.