Remove Duplicates in Sorted Linked List

Introduction

Linked Lists often contain duplicate values, especially when data is sorted.

This problem focuses on removing duplicate nodes from a sorted linked list while maintaining the original structure.

Problem Statement

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

Conditions:

• The list is already sorted
• Do not use extra space
• Modify the list in-place

Examples

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

Example 2:
Input: 2 -> 2 -> 2 -> 2 -> 2
Output: 2

Intuition

Since the list is sorted, duplicates will always be adjacent.

So:

• Compare current node with next node
• If equal -> skip the next node
• Else -> move forward

Approach

Algorithm Steps

• Start with current = head

• Traverse the list:

  • If current.val == current.next.val:
    • Skip duplicate -> current.next = current.next.next
  • Else:
    • Move to next node

• Continue until end

Code (Python)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeDuplicates(head):
    current = head

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

    return head

Step-by-Step Explanation

For 2 -> 2 -> 4 -> 5:

• Compare 2 and 2 -> remove duplicate
• Move to 4 -> no duplicate
• Move to 5 -> no duplicate

Final → 2 -> 4 -> 5

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Conclusion

Removing duplicates from a sorted linked list is a simple yet powerful problem that demonstrates efficient pointer usage and optimization techniques.