245. Remove Duplicates From an Unsorted Linked List

A singly linked list contains n integer values, not necessarily sorted, possibly with duplicates anywhere in the list. Remove every node whose value already appeared earlier in the list, keeping only the first occurrence of each value in its original position. Print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers, not necessarily sorted and possibly containing duplicates. Output: Print the remaining values after removing later duplicates, in their original order, space-separated.

1 <= n <= 10^5

This is the direct 'no sortedness guarantee' counterpart to the sorted-list version - comparing the two side by side is a great way to internalize exactly what sortedness buys you algorithmically.

Remove duplicate values from a linked list that ISN'T sorted, keeping only the first occurrence of each value. Brute force: For every node, scan every OTHER node in the list directly to check if its value repeats earlier - this costs O(n²), too slow for large lists, and unnecessary given hash sets provide O(1) lookups. Optimised: Since the list isn't sorted, duplicates can appear ANYWHERE, so adjacent-only comparisons (as used for the sorted version) don't work here - a hash set of values already seen lets you decide in O(1) whether to keep or delete each node in a single linear pass, at the cost of O(n) extra memory.

Walk the list with a pointer, and for every node, scan all nodes that come before it in the list to check whether its value already appeared; if it has, unlink the current node from the list. This preserves the required original order of first occurrences since nothing is reordered, only removed, but comparing against every earlier node for every node makes it quadratic. Time: O(n^2) Space: O(1)

Walk the list once, maintaining a self-balancing ordered set (such as a TreeSet) of values already seen. For each node, check membership in O(log n); if the value is already present, unlink the node, otherwise insert its value into the set and move on. Because membership queries take only O(log n) instead of a full O(n) rescan of prior nodes, and the list is never sorted or reordered (so the required original positions of first occurrences are preserved), this is a genuine improvement over the brute force while remaining fully correct for this problem. Time: O(n log n) Space: O(n)

Walk the list once, maintaining a hash set of values already seen. For each node, check membership in the hash set in O(1) average time; if present, unlink the current node from the list, otherwise add its value to the set. This keeps every first occurrence exactly in its original position (never sorting the list, which would violate the problem's ordering requirement) while doing only a single linear pass with constant-time lookups, the best possible approach short of an algorithm that avoids extra space entirely. Time: O(n) Space: O(n)

1. Maintain a hash set of every value already seen so far. 2. Walk the list once: for each node, if its value is ALREADY in the seen set, unlink (delete) it; otherwise, add its value to the seen set and move on.

Time: O(n) - one single pass, with O(1) hash-set lookups at each node. Space: O(n), for the hash set of seen values (the necessary tradeoff for handling unsorted duplicates efficiently).

n = 1 (no duplicates possible), a list where every value is identical (only the first survives), and n = 10^5 for performance.

Be ready to state clearly WHY the sorted version's O(1)-space trick (checking only adjacent nodes) doesn't apply here - the lack of ordering is exactly what forces the O(n) hash-set memory tradeoff.