In a sorted singly linked list, how can duplicates be removed in O(n) time and O(1) space?

• A. Use a hash set to track seen values.
• B. Traverse; if current node's value equals the next node's value, skip the next by linking current.next to current.next.next; otherwise move forward.
• C. Reverse the list and remove duplicates at the end.
• D. Create a new list by copying only unique values.

Answer: (B)

In a sorted singly linked list, duplicates show up next to each other, so you can remove them with a single in-place pass. Keep a pointer to the current node, and while the current node and its next exist, compare their values. If they’re equal, bypass the next node by setting current.next to current.next.next, effectively deleting one duplicate without allocating new nodes. If they’re different, move the current pointer forward. This continues until you reach the end. Because you only update pointers and traverse each node once, the time is O(n) and the space is O(1).

Using a hash set would track seen values and require extra space, so it isn’t O(1) space. Creating a new list with only unique values uses additional nodes and memory. Reversing the list and removing duplicates later adds extra steps without improving the core in-place efficiency.