Deduplicate a Linked List
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given a singly linked list, remove duplicate values in-place. Variant A (sorted list): delete repeated nodes so each value appears once using O(
1) extra space. Variant B (unsorted list): delete duplicates while preserving the first occurrence; provide two solutions—
(
1) using a hash set and
(
2) without extra memory using the runner technique. Define your ListNode type, explain correctness, analyze time and space complexity for each approach, and include tests for edge cases (empty list, single node, all duplicates, no duplicates).
Quick Answer: This question evaluates proficiency in linked list manipulation, in-place data structure modification, and reasoning about time-space trade-offs for removing duplicate elements.
Part 1: Deduplicate a Sorted Singly Linked List
You are given a sorted singly linked list. Remove duplicate values in-place so that each value appears exactly once.
Because this platform uses JSON-friendly I/O, the linked list is provided as a Python list of values in non-decreasing order. Your function should internally define a ListNode type, build the linked list, remove duplicates by rewiring next pointers, and return the final linked list as a Python list.
Since the list is sorted, any duplicates will appear next to each other.
Constraints
- 0 <= len(values) <= 200000
- -10^9 <= values[i] <= 10^9
- `values` is sorted in non-decreasing order
Examples
Input: []
Expected Output: []
Explanation: Edge case: an empty list stays empty.
Input: [5]
Expected Output: [5]
Explanation: Edge case: a single node has no duplicates to remove.
Hints
- In a sorted list, duplicate values are always adjacent.
- Use one pointer that compares the current node with its next node; only move forward when the values differ.
Part 2: Deduplicate an Unsorted Singly Linked List While Preserving First Occurrences
You are given an unsorted singly linked list. Remove duplicate values while preserving the first occurrence of each value.
Because this platform uses JSON-friendly I/O, the linked list is represented as a Python list. Implement both approaches inside one function:
- If `method == 'hash'`, use a hash set to remove duplicates in linear time on average.
- If `method == 'runner'`, do not use extra memory for seen values; instead, use the runner technique to delete later duplicates.
Your function should internally define a ListNode type, build the linked list, perform the requested deduplication, and return the final linked list as a Python list.
Constraints
- 0 <= len(values) <= 5000
- -10^9 <= values[i] <= 10^9
- `method` is either `'hash'` or `'runner'`
Examples
Input: ([], 'hash')
Expected Output: []
Explanation: Edge case: an empty list stays empty.
Input: ([9], 'runner')
Expected Output: [9]
Explanation: Edge case: a single node has no duplicates.
Hints
- To preserve first occurrences, keep the first time a value appears and remove only later nodes with the same value.
- The runner technique fixes one node at a time and scans the rest of the list to delete matching values.