Remove Duplicates from Sorted List (LC 83)

Pattern: Linked List - In-Place Modification
Difficulty: Easy
Key Concept: Skip duplicate nodes by modifying next pointers in a single pass

1. 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 sorted as well.

Constraints (typical):

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

---

2. Algorithm (Single Pass)

Idea: Because the list is sorted, duplicates are adjacent. Walk with one pointer cur; if cur.next has the same val, skip it by setting cur.next = cur.next.next. Otherwise advance cur.

Pseudocode:

cur = head
while cur != null AND cur.next != null:
    if cur.val == cur.next.val:
        cur.next = cur.next.next   // skip duplicate node
    else:
        cur = cur.next
return head

---

3. Beginner Analysis

• Sorted order means all equal values are contiguous, so you only ever compare a node with its immediate successor.
• You reuse the first occurrence of each value and unlink the rest; no new nodes are allocated.
• In Java, unlinked nodes have no references from your list anymore and can be garbage collected — there is no delete like in C++.
• Always check cur.next != null before reading cur.next.val to avoid null pointer errors.

---

4. Dry Run — [1,1,2,3,3]

Step	cur.val	cur.next	Action	List (conceptual)
0	1	1	1==1 → skip next	1 → 2 → 3 → 3
1	1	2	1≠2 → advance	same
2	2	3	2≠3 → advance	same
3	3	3	3==3 → skip next	1 → 2 → 3
4	3	null	stop	1 → 2 → 3

---

5. Brute Force Java — HashSet (Unnecessary When Sorted)

Shown for comparison: track seen values (works on unsorted lists too, but uses extra space and ignores the sorted property).

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

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

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

---

6. Optimal Java — Single Pointer

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

---

7. Java & Language Tricks

Topic	Note
GC	Skipped nodes become unreachable; no manual free (unlike C++).
Null safety	Loop condition must ensure cur.next exists before cur.next.val.
Why not HashSet for LC 83?	Sorted input makes O(1) space single pass strictly better.

---

8. Complexity

Approach	Time	Space
HashSet	O(n)	O(n)
Single pass (optimal)	O(n)	O(1)

n = number of nodes.