Remove duplicates from a singly linked list
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
You are given the head of a **singly linked list** of integers. Modify the list **in place** so that it contains **only the first occurrence** of each value (i.e., remove any node whose value has already appeared earlier in the list).
- Each node has fields:
- `data` (integer)
- `next` (reference to next node, or `null` at the tail)
- The **relative order** of the remaining nodes must stay the same.
Return the head of the updated linked list.
### Examples
1. Input: `3 -> 4 -> 3 -> 6`
Output: `3 -> 4 -> 6`
2. Input: `3 -> 4 -> 3 -> 2 -> 6 -> 1 -> 2 -> 6`
Output: `3 -> 4 -> 2 -> 6 -> 1`
Quick Answer: This question evaluates understanding of singly linked list data structures and in-place node manipulation to remove repeated values while preserving relative order, testing competencies in pointer management and duplicate-detection.
You are given the head of a **singly linked list** of integers. Modify the list **in place** so that it contains **only the first occurrence** of each value (i.e., remove any node whose value has already appeared earlier in the list). The **relative order** of the remaining nodes must stay the same. Return the head of the updated linked list.
Each node has a `data` (integer) field and a `next` reference (or `null` at the tail).
**Marshalling for this console:** the linked list is represented as an array of the node values in order (the sequence of `data` fields from head to tail). Your function receives this array and must return the array of values that remain after removing every node whose value already appeared earlier — preserving the original order.
### Examples
1. Input: `[3, 4, 3, 6]` (i.e. `3 -> 4 -> 3 -> 6`)
Output: `[3, 4, 6]`
2. Input: `[3, 4, 3, 2, 6, 1, 2, 6]`
Output: `[3, 4, 2, 6, 1]`
Constraints
- 0 <= number of nodes <= 10^5
- -10^9 <= node value (data) <= 10^9
- The relative order of the remaining nodes must be preserved
- Keep only the first occurrence of each value
Examples
Input: [3, 4, 3, 6]
Expected Output: [3, 4, 6]
Explanation: The second 3 is a duplicate of the earlier 3, so it is removed; 4 and 6 are unique.
Input: [3, 4, 3, 2, 6, 1, 2, 6]
Expected Output: [3, 4, 2, 6, 1]
Explanation: The second 3, the second 2, and the second 6 are all later duplicates and get removed, leaving the first occurrence of each value in order.
Hints
- Walk the list once from head to tail, tracking which values you have already seen in a hash set.
- Keep a node only the first time you encounter its value; skip (unlink) any node whose value is already in the set.
- A single pass with a set gives O(n) time and O(n) extra space — no need to compare every pair of nodes.