---

1. Problem Summary

You are given the head of a sorted singly linked list.
Your task is to remove all nodes that have duplicate values, meaning:

• If a value appears more than once,
• all occurrences of that value must be removed (not just reduced to one).

Return the head of the updated list containing only distinct values.

Example interpretation:
Input:

1 → 2 → 3 → 3 → 4 → 4 → 5

Values 3 and 4 appear more than once, so remove them entirely.

Output:

1 → 2 → 5

---

2. Key Insights

Sorted list property is crucial

Duplicates will always be adjacent, so detection is easy.

We must remove all nodes with repeated values

This differs from Problem 83, where duplicates are collapsed into one node.

Dummy head simplifies edge cases

If the first values are duplicates, original head must be removed.
Dummy node ensures we always have a stable predecessor pointer.

Two-pointer strategy works best

We use:

• prev → last confirmed unique node
• current → node under inspection

Removal rule

If current.val == current.next.val, advance until value changes, then skip entire block.

---

3. Approach

Dummy-head traversal with duplicate skipping

Steps:

1. Create a dummy node pointing to head
2. Initialize: prev = dummy current = head
3. While current exists:
   • If current has duplicates (current.next exists and both values equal):
     • Advance current until value changes (skipping duplicates)
     • Link prev.next to current.next (removes entire duplicate block)
   • Else (value unique):
     • Move prev forward to current
     • Move current forward
4. Return dummy.next as new head

This ensures only non-duplicate nodes remain.

---

4. Time and Space Complexity

Time Complexity: O(N)

Each node visited at most twice.

Space Complexity: O(1)

Constant extra pointers, no auxiliary containers.

---

5. Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode current = head;

        while (current != null) {
            // Detect duplicates
            boolean isDuplicate = false;

            while (current.next != null && current.val == current.next.val) {
                current = current.next;
                isDuplicate = true;
            }

            if (isDuplicate) {
                // Skip entire duplicate block
                prev.next = current.next;
            } else {
                prev = prev.next;
            }

            current = current.next;
        }

        return dummy.next;
    }
}

---

6. Dry Run Examples

Example 1

Input:

1 → 2 → 3 → 3 → 4 → 4 → 5

Walk-through:

• 1 unique → keep
• 2 unique → keep
• 3 duplicates → skip both
• 4 duplicates → skip both
• 5 unique → keep

Output:

1 → 2 → 5

---

Example 2

Input:

1 → 1 → 1 → 2 → 3

• 1 repeated → remove all three
• 2 unique
• 3 unique

Output:

2 → 3

---

Example 3

Input:

1 → 2 → 2 → 2

• 1 unique
• 2 repeated three times → remove

Output:

1

---

Example 4

Input:

3 → 3 → 3

All duplicates removed

Output:

empty list (null)

---

Example 5

Input:

1 → 2 → 3 → 4

No duplicates

Output:

1 → 2 → 3 → 4

---

7. Why This Solution Works

• Sorted order guarantees adjacent duplicates
• Dummy node handles head-removal edge case
• prev pointer ensures safe list rewiring
• Skips full duplicate runs, not individual nodes
• No extra memory or value rewriting needed

---

8. Common Mistakes

1. Treating problem like LC83 and keeping one copy
2. Forgetting to remove duplicate blocks completely
3. Not handling duplicate sequence at the head
4. Advancing prev incorrectly when duplicates found
5. Pointer skipping leading to lost nodes or cycles