Remove Duplicates from Sorted List (LC 83)

Pattern: Single pointer traversal (sorted input makes duplicates adjacent)
Difficulty: Easy
Key Concept: Because the list is sorted, duplicates appear next to each other — skip next when current.val == current.next.val without a hash set.

Problem Statement

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

Input: head of a sorted ListNode chain.

Output: head of the modified list (same head node if the first value is kept; structure may skip nodes).

---

1. Algorithm & Pseudocode

Brute force: HashSet (unnecessary here)

1. Create HashSet<Integer> seen.
2. Use a dummy node or track prev and cur.
3. Walk the list: if cur.val is already in seen, set prev.next = cur.next (skip cur); else add cur.val to seen and move prev to cur.
4. Advance cur appropriately.

This works for unsorted lists too, but uses O(n) extra space and ignores the fact that sorted duplicates are always adjacent.

Optimal: one pointer

1. If head is null, return null.
2. cur = head.
3. While cur.next != null:
   • If cur.val == cur.next.val, set cur.next = cur.next.next (drop the duplicate node; do not move cur yet — the new cur.next might also be a duplicate).
   • Else cur = cur.next.
4. Return head.

Why not advance cur when skipping: After cur.next = cur.next.next, the next node might still equal cur.val (e.g., 1→1→1). Staying on cur collapses all consecutive duplicates.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Sorted ⇒ adjacent duplicates: If values are non-decreasing, any duplicate of cur.val must appear immediately in cur.next, cur.next.next, etc. No need to remember old values in a set.

Skipping a node: Setting cur.next to the node after the duplicate detaches the duplicate from the list. In Java, nothing explicitly “frees” the node; garbage collection reclaims unreachable objects.

Single pass: Each edge is examined a constant number of times — O(n) time, O(1) space.

Brute force as a teaching contrast: A HashSet is overkill when the input is sorted, but it shows the general “seen values” idea used in unsorted duplicate removal.

---

3. The Dry Run

Initial list: 1 → 1 → 2 → 3 → 3 (values shown).

Step	cur.val	cur.next (before)	cur.next.val	Action	List after (conceptually)
Init	1	second 1	1	—	1 → 1 → 2 → 3 → 3
1	1	second 1	1	cur.next = cur.next.next	1 → 2 → 3 → 3
2	1	2	2	values differ → cur = cur.next	(cur now at 2)
3	2	3	3	differ → cur = cur.next	(cur at first 3)
4	3	second 3	3	cur.next = cur.next.next	1 → 2 → 3
5	3	null	—	cur.next null → exit	1 → 2 → 3

Result: Each value appears once.

---

4. Java Solution

Brute Force

import java.util.HashSet;
import java.util.Set;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Set<Integer> seen = new HashSet<>();
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (seen.contains(cur.val)) {
                prev.next = cur.next;
            } else {
                seen.add(cur.val);
                prev = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

Time: O(n).
Space: O(n) for the set (unnecessary when the list is already sorted).

Optimal

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

Time: O(n).
Space: O(1).

---

5. The “Java vs. Others” Edge

• Memory management: In C++, removing nodes often requires delete (or smart pointers) to avoid leaks. In Java, once no reference points to a detached ListNode, the garbage collector reclaims it. You only need to fix next pointers.
• No pointer arithmetic: Like other list problems, you use cur.next, not raw address math.
• Sorted property: The optimal solution depends on sorted order; the HashSet version would still work if the list were unsorted (at the cost of space).
• Dummy node in brute force: A common Java/C++ trick so prev always has a node to update when deleting the first duplicate; the optimal solution often skips dummy because we only skip forward from head when head stays the smallest value.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	HashSet; general but redundant for sorted input.
Optimal	O(n)	O(1)	Exploit adjacency of duplicates; only pointer rewiring.