How do you remove duplicates from an unsorted singly linked list with extra storage?

• A. Sort the list first and then remove duplicates.
• B. Use a hash set to track seen values and remove duplicates as you traverse; O(n) time, O(n) space.
• C. Use two nested loops without extra storage.
• D. Compare each node with all following nodes.

Answer: (B)

Using a hash set to track values you’ve already seen lets you remove duplicates in a single pass. As you walk through the unsorted list, if you encounter a value you’ve seen before, unlink the current node by making the previous node point to current.next; if it’s new, add the value to the set and move on. This approach works well because you don’t rely on any particular order—the check for duplicates is constant time on average, so every node is processed once, yielding O(n) time and O(n) space. The trade-off is the extra storage to hold the seen values. Sorting first could work but would typically take O(n log n) time and isn’t as efficient if you’re allowed to use extra storage. Approaches that compare each node with all following nodes don’t use extra storage and run in O(n^2) time, which is slower for larger lists.