7.6 Remove Duplicates from Sorted List

7.6.1 Problem Metadata

7.6.2 Description

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.

7.6.3 Examples

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

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

7.6.4 Constraints

  • The number of nodes is in the range [0, 300]
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order

7.6.5 Solution - In-Place Skip

7.6.5.1 Walkthrough

Since the list is sorted, duplicates are always adjacent. We simply traverse and skip over duplicate nodes.

Core Strategy:

  1. For each node, compare its value with the next node’s value
  2. If equal, skip the next node by updating curr.next
  3. If different, move to the next node

Example: Remove duplicates from [1,1,2,3,3]:

curr at 1: curr.val (1) == curr.next.val (1) → skip: 1 → 2 → 3 → 3
curr at 1: curr.val (1) != curr.next.val (2) → move curr to 2
curr at 2: curr.val (2) != curr.next.val (3) → move curr to 3
curr at 3: curr.val (3) == curr.next.val (3) → skip: 1 → 2 → 3 → null
curr at 3: curr.next is null → done
Result: [1,2,3]

7.6.5.2 Analysis

  • Time Complexity: O(n) - Each node visited at most once
  • Space Complexity: O(1) - Only pointer variables used

7.6.5.3 Implementation Steps

  1. Start with curr at head.
  2. While curr and curr.next exist, compare values.
  3. If duplicate, skip: curr.next = curr.next.next.
  4. Otherwise, advance: curr = curr.next.
  5. Return head.

7.6.5.4 Code - 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;
}