How would you remove duplicates from an unsorted linked list in O(n) time using extra space?

• A. Two-pointer technique without extra space.
• B. Use a hash set to track seen values; delete any node whose value has appeared before.
• C. Reverse the list and remove duplicates.
• D. Sort the list first then remove duplicates.

Answer: (B)

The idea being tested is that keeping track of what you’ve already seen lets you remove duplicates in a single pass. By using a hash set to store values as you traverse the list, you can decide in constant time whether the current node is a duplicate. Walk from the head to the end, and for each node:

• if its value is already in the set, update the previous node’s next pointer to skip the current node;

• if it isn’t, add the value to the set and move forward.

This way you visit each node once, giving linear time, and the hash set grows to hold all distinct values, giving linear extra space.

Why this is the best fit here: the hash-set approach directly achieves O(n) time for an unsorted list by eliminating duplicates on the fly, and uses the extra space to remember what’s seen so far. Other methods either slow you down (for example, needing to scan ahead for duplicates they pass each node, leading to O(n^2) in general), or require sorting first (which costs at least O(n log n) time and may complicate in-place constraints).