Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

Master this topic with zero to advance depth.

Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Visual Representation

List: 1 -> 1 -> 2 -> 3 -> 3 1. 1 == 1. 1.next points to 2. 2. 2 != 1. Move to 2. 3. 3 == 3. 3.next points to null. Result: 1 -> 2 -> 3
Easy

Examples

Input: head = [1,1,2,3,3]
Output: [1,2,3]
Approach 1

Level I: Iterative

Intuition

Since the list is sorted, nodes with the same value will be adjacent. Traverse the list, and if a node's value equals its next node's value, skip the next node.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->1->2.

  1. head=1, next=1. Val 1 == 1. 1.next = 1.next.next = 2.
  2. head=1, next=2. Val 1 != 2. head=2.
  3. head=2, next=null. End.
java
public ListNode deleteDuplicates(ListNode head) {
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) curr.next = curr.next.next;
        else curr = curr.next;
    }
    return head;
}

⚠️ Common Pitfalls & Tips

Only works on sorted lists. For unsorted lists, a hash set would be needed.

Approach 2

Level II: Recursive

Intuition

The recursive approach checks the head and its next node. If they have the same value, it skips the current head and returns the result of the recursive call on the next node.

⏱ O(N)💾 O(N) recursion stack

Detailed Dry Run

1->1->2.

  1. head=1, next=1. Val 1 == 1. Return deleteDuplicates(1.next).
  2. head=1, next=2. Val 1 != 2. head.next = deleteDuplicates(2). Return head.
  3. head=2, next=null. Return head.
java
public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) return head;
    head.next = deleteDuplicates(head.next);
    return head.val == head.next.val ? head.next : head;
}

⚠️ Common Pitfalls & Tips

Recursion depth is proportional to the number of nodes.

Approach 3

Level III: Iterative with Sentinel (Dummy Node)

Intuition

Using a dummy node isn't strictly necessary for this problem (since the head never changes), but it's a good practice to ensure consistency across all linked list problems.

  1. Initialize a dummy node pointing to head.
  2. Iterate through the list using a curr pointer.
  3. Compare curr with curr.next and skip duplicates.
⏱ O(N)💾 O(1)

Detailed Dry Run

Dummy -> 1 -> 1 -> 2.

  1. curr = 1. curr.next = 1. Match. curr.next = 2.
  2. curr = 1. curr.next = 2. No match. curr = 2.
  3. curr = 2. curr.next = null. End.
java
public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode dummy = new ListNode(-101); // Constraint: val is usually -100 to 100
    dummy.next = head;
    ListNode curr = head;
    while (curr != null && curr.next != null) {
        if (curr.val == curr.next.val) curr.next = curr.next.next;
        else curr = curr.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Ensure the dummy value doesn't conflict with valid node values.

← Previous QuestionPalindrome Linked List
Next Question →Linked List Cycle II