Remove Duplicates from a Sorted Linked List

Introduction

In this problem, we are given a sorted linked list. Since the list is already sorted, duplicate elements will always appear next to each other.

The task is to remove duplicate nodes such that each element appears only once.

Problem Statement

Given the head of a sorted linked list:

• Remove all duplicate nodes

• Return the modified list

• Do not use extra space

Example

Input:

2 -> 2 -> 4 -> 5

Output:

2 -> 4 -> 5

Solution Code

def removeDuplicates(head):
    current = head

    while current and current.next:
        if current.data == current.next.data:
            # remove duplicate node
            current.next = current.next.next
        else:
            current = current.next

Approach Used: In-Place Traversal

Idea

Since the list is sorted:

• Duplicate values will be adjacent

• We can simply compare current node with next node

How It Works

1. Start from the head node

2. Traverse the list:

   • If current.data == current.next.data:

     • Skip the next node

   • Else:

     • Move to the next node

3. Continue until the end of the list

Why This Approach Was Chosen

• No extra space required (in-place)

• Takes advantage of sorted property

• Simple and efficient logic

Alternative Approach

• Using Hash Set
   Works for unsorted lists
   Uses extra space

Why not used here?
Because the list is already sorted, making this simpler approach possible

Time and Space Complexity

• Time Complexity: O(n)

• Space Complexity: O(1)

 Observation

• Sorted nature ensures duplicates are adjacent

• We only need to compare current and next node

• No need for nested loops

Edge Cases

• Empty list = return null

• Single node = no duplicates

• All elements same = only one node remains

Conclusion

Removing duplicates from a sorted linked list is efficient when done in-place. By leveraging the sorted property, we can easily eliminate duplicate nodes in a single traversal without using extra space.