#82 Remove Duplicates from Sorted List II

frequently reported atBloomberg Microsoft Amazon

the problem

In plain words

Given the head of a sorted linked list, delete every node whose value appears more than once, so that only values appearing exactly once remain. Return the (still sorted) result.

in head = [1,2,3,3,4,4,5]

out [1,2,5]

in head = [1,1,1,2,3]

out [2,3]

0 ≤ number of nodes ≤ 300
-100 ≤ Node.val ≤ 100
The list is sorted in ascending order

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Sorted means all copies of a value sit together in one run. Keep prev on the last node you are sure to keep (a dummy at first, since the head may go). When curr starts a run, skip the whole run and link prev past it.

solutions

From brute force to optimal

Count values in a LinkedHashMap (keeps insertion order — here the input arrives sorted), then build a new list of the values counted once.

count.merge(val, 1, Integer::sum) for every node.
For each entry with count 1, append a new node.

timeO(n)

One pass to count, one over the distinct values.

spaceO(n)

The map plus new nodes.

javajava.util.*

1class Solution {2    public ListNode deleteDuplicates(ListNode head) {3        Map<Integer, Integer> count = new LinkedHashMap<>();  // keeps the sorted order of first sight4        for (ListNode p = head; p != null; p = p.next) count.merge(p.val, 1, Integer::sum);5        ListNode dummy = new ListNode();6        ListNode tail = dummy;7        for (Map.Entry<Integer, Integer> e : count.entrySet()) {8            if (e.getValue() == 1) {                          // keep values seen exactly once9                tail.next = new ListNode(e.getKey());10                tail = tail.next;11            }12        }13        return dummy.next;14    }15}

If curr and curr.next share a value, move curr past every node with that value and set prev.next = curr. Otherwise keep curr: prev = curr.

dummy → head; prev = dummy; curr = head.
If curr.next has the same value: remember it, skip the run, prev.next = curr.
Else prev = curr; curr = curr.next.
Return dummy.next.

timeO(n)

curr moves forward over every node exactly once.

spaceO(1)

Two references and a dummy.

javajava.util.*

1class Solution {2    public ListNode deleteDuplicates(ListNode head) {3        ListNode dummy = new ListNode(0, head);   // the head itself may be a duplicate4        ListNode prev = dummy;                    // last node we are sure to keep5        ListNode curr = head;6        while (curr != null) {7            if (curr.next != null && curr.val == curr.next.val) {8                int dup = curr.val;9                while (curr != null && curr.val == dup) curr = curr.next; // skip the whole run10                prev.next = curr;                 // unlink every copy at once11            } else {12                prev = curr;                      // a unique value: keep it13                curr = curr.next;14            }15        }16        return dummy.next;17    }18}

in the room

How to say it in the interview

talk track

Contrast with LC 83 (keep one copy): here every copy goes, so you need the node before the run — prev.
Dummy, because the head itself may be deleted (example 2).
Only advance prev when the current value is unique.

traps

Advancing prev right after removing a run — the next node might start another run ([1,1,2,2]).
Returning head instead of dummy.next when the first values are duplicates.

what they ask next

Follow-ups

Keep one copy of each value instead (LC 83)?

Simpler: if curr.val == curr.next.val, curr.next = curr.next.next; else curr = curr.next. No dummy needed — the head always stays.

What if the list were unsorted?

Count values in a HashMap in a first pass, then remove every node whose count is above 1 in a second pass (with a dummy).

before you submit

Edge cases to test

Empty list → null.
Everything repeats ([1,1,2,2]) → an empty list.
The head repeats → the head changes.
The tail repeats → the list ends at prev.

practise next