Practice/Oracle/Leetcode 1836. Remove Duplicates From an Unsorted Linked List

Leetcode 1836. Remove Duplicates From an Unsorted Linked List

CodingMust

Problem

Given the head of an unsorted linked list, remove all nodes that have values appearing more than once in the list. Return the head of the modified linked list.

If a value appears two or more times anywhere in the linked list, all nodes with that value should be removed from the list.

The linked list is not sorted, so duplicate values may appear at any positions throughout the list.

Requirements

1. Remove all nodes whose values appear more than once in the linked list
2. Preserve the relative order of the remaining nodes
3. Return the head of the modified linked list
4. Handle edge cases including empty lists and lists where all values are duplicates

Constraints

• The number of nodes in the list is in the range [0, 10^5]
• 1 <= Node.val <= 10^5
• The linked list may contain duplicate values scattered throughout
• You should solve this with a time complexity of O(n) and space complexity of O(n)

Examples

Example 1:

Input: head = [1, 2, 3, 2] Output: [1, 3] Explanation: The value 2 appears twice, so both nodes with value 2 are removed. Only nodes with values 1 and 3 remain.

Example 2:

Input: head = [2, 1, 1, 2, 3] Output: [3] Explanation: Value 1 appears twice and value 2 appears twice. Only the node with value 3 appears once, so it's the only node remaining.

Example 3:

Input: head = [3, 3, 3] Output: [] Explanation: All nodes have the same value which appears three times. Since all values are duplicates, the result is an empty list.

Example 4:

Input: head = [1, 2, 3, 4, 5] Output: [1, 2, 3, 4, 5] Explanation: All values appear exactly once, so no nodes are removed.