Medium · Dummy Head and Run Skipping
Understand → Visualise → Practice.
A sorted linked list is represented by values. Remove every value that occurs more than once and return the remaining traversal.
Because the list is sorted, duplicates sit in runs. Use a dummy head; whenever a run has more than one node, link past the entire run.
It lets you delete the first real node without special cases.
From the current node, advance while the next value is the same.
Keep the node only if its run has length 1; otherwise link prev.next past the whole run.
O(n) time and O(1) extra space.
Keeping one copy of a repeated value (as in plain deduplication) is not what's asked; every copy goes.
Read the full guide first: Linked Lists.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.