A library catalog holds a sorted singly linked list of ISBN numbers. Overnight ingest retried a batch and wrote the same ISBN twice in a row. The catalog should show each book once. The intern version dumped every number into a HashSet and allocated a new chain of unique values. The numbers were unique. The nodes were not. The shelf-location service that still held a node from the overnight ingest was looking at a successor the “deduped” catalog no longer used.

Deduping a sorted singly linked list means unlinking adjacent twins so each value appears once, on the same nodes you were given. The linked list post owns splice, dummy nodes, and why get(i) walks. Here we only care about one walk and the skip that stays put until the run is gone.

This is keep-one-of-each. It is not “delete every value that appeared more than once, including the original.” That is a different problem; interviewers name it as a follow-up.

The problem

Given the head of a sorted singly linked list, delete duplicate values so each value appears once. Return the head. An empty list and a single node are already unique. Because the list is sorted, duplicates are adjacent — you never hunt a later copy of a value you already kept.

1 → 1 → 2 → null                 →  1 → 2 → null
1 → 1 → 2 → 3 → 3 → null         →  1 → 2 → 3 → null
1 → 1 → 1 → 2 → null             →  1 → 2 → null
(empty)                          →  empty
1 → null                         →  1 → null

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

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

Note: In-place means the same node objects, new next links. Copying unique values into a fresh chain passes a value-order test and fails any test that identity of nodes matters — or any follow-up that said O(1) extra space. Reverse Linked List already taught that trap.

HashSet, or a copied chain, is the honest brute

Walk the list, record every val in a LinkedHashSet (first-seen order), then allocate a new chain. Unique numbers. New objects. Extra hash table. The list was already sorted; you did not need either.

ListNode deleteDuplicatesCopied(ListNode head) {
    Set<Integer> unique = new LinkedHashSet<>();
    for (ListNode n = head; n != null; n = n.next) {
        unique.add(n.val);
    }
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    for (int val : unique) {
        tail.next = new ListNode(val);
        tail = tail.next;
    }
    return dummy.next;
}

At a handful of ISBNs this is a rounding error. In production you paid O(n) extra nodes and a hash table for a question the sort already answered: is current.next the same value as current? A HashSet while unlinking in place keeps identity and still wastes the sorted gift. Unsorted input is when the set earns its keep.

One walk: skip the equal neighbor

Start current at head. While current and current.next are both non-null:

  • If current.val == current.next.val, splice out the neighbor: current.next = current.next.next. Do not advance. A run of three is two skips from the same node.
  • Otherwise the next value is new. Advance: current = current.next.

Head never moves. You always keep the first node of a value, so the entry point of the list is still the first unique value.

Walk 1 → 1 → 1 → 2 → null:

start:  current=1 → 1 → 1 → 2

skip:   1.next = 1.next.next     1 → 1 → 2     current still first 1
skip:   1.next = 1.next.next     1 → 2         current still first 1
advance: values differ           current=2
done:   current.next is null

return head  (first 1)

The Java is that walk:

ListNode deleteDuplicates(ListNode head) {
    ListNode current = head;
    while (current != null && current.next != null) {
        if (current.val == current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return head;
}

Time is O(n) — each node is visited once. Space is O(1) besides the one cursor. No dummy: the first occurrence of the first value stays the head.

Advancing after a skip leaves a longer run on the floor. 1 → 1 → 1 would become 1 → 1 if you moved forward after unlinking once. Stay on current until the neighbor differs.

Empty list: current is already null, the loop never runs, you return null. One node: current.next is null, same story, you return that node. No special cases.

What interviewers usually poke next

  • Delete every duplicated value entirely. Not “keep one of each” — drop the original too, so 1 → 1 → 2 becomes 2, and 1 → 1 becomes empty. Head can leave. You want a dummy and a skip of the whole run, not a skip of the neighbor. Name the difference out loud before you write code.
  • Unsorted input. Then adjacent is not a guarantee. A HashSet of seen values (or sort, then this walk) is the honest bill. Say why this prompt did not need it.
  • Keep at most k copies. Same walk; count the run and skip only after k.
  • Doubly linked. You also rewire prev on the unlinked node. The idea is the same; the bug surface doubles. The layout post already has that variant.
  • Recursive version. If head.val == head.next.val, return the dedup of head.next; else set head.next to the dedup of the suffix. Mention the O(n) stack bill; iterative skip is the default.

You are done with this problem when you can collapse 1 → 1 → 1 → 2 on a whiteboard without a set, and you can say why you stay on current after a skip.