103. Remove Duplicates From a Sorted Linked List

A sorted singly linked list has n values, possibly with consecutive duplicates. Remove duplicate values so each distinct value appears only once, and print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers in sorted order, possibly with consecutive duplicates. Output: Print the list with duplicates removed, each distinct value appearing once, space-separated.

1 <= n <= 10^5

Sortedness is precisely what turns an otherwise O(n) MEMORY problem (needing a seen-set) into an O(1) memory one - recognizing when a problem's stated guarantee (sorted order) eliminates the need for extra storage is a valuable habit.

Remove duplicate values from an already-sorted linked list, keeping just one copy of each distinct value. Brute force: Use a hash set to track every distinct value seen, checking every node against it regardless of position - this works but is unnecessary extra memory when sortedness already guarantees duplicates are adjacent. Optimised: Because the list is SORTED, comparing only each node to its IMMEDIATE next neighbor is sufficient to catch every duplicate - no hash set or lookahead beyond one node is ever needed, achieving the removal in a single linear pass with O(1) extra space.

For each node in the list, compare its value against every node that comes after it, and if a match is found, unlink (remove) that later node. This treats the problem generally, without assuming anything about ordering, and correctly removes all duplicate values wherever they occur, but comparing every node to every later node makes the work grow quadratically with the list's length. Time: O(n^2) Space: O(1)

Use a hash set to record which values have already been seen while making a single pass through the list; whenever the current node's value is already in the set, unlink it from the list, otherwise add its value to the set and move on. This works even on an unsorted list and only requires one pass, a large improvement over the nested comparison of brute force, at the cost of memory to store the seen values. Time: O(n) Space: O(n)

Because the list is sorted, any duplicate values are guaranteed to sit immediately next to each other - there's no need to remember values from far earlier in the list. Walk through with a single pointer, and at each node compare its value to the very next node's value: if they're equal, skip over (unlink) the next node and check again; if they differ, advance the pointer. This exploits the sorted property to remove all duplicates in a single pass without any auxiliary memory at all. Time: O(n) Space: O(1)

1. Since the list is sorted, any duplicate of a value is guaranteed to sit IMMEDIATELY ADJACENT to it - no need to look further away. 2. Walk the list once, comparing each node to the very next one. 3. If they're equal, skip over (unlink) the next node instead of advancing past it; otherwise, move forward normally.

Time: O(n) - one single pass through the list. Space: O(1) - no extra data structure needed.

n = 1 (unchanged), a list where every value is identical (a single output value), and n = 10^5 for performance.

Be ready to contrast this immediately with 'Remove Duplicates From an UNSORTED Linked List' - the sorted version needs only adjacent comparisons, while the unsorted version genuinely requires a hash set, since duplicates can appear anywhere.