Deduplicate a Linked List
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
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
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.
Input: [7, 7, 7, 7]
Expected Output: [7]
Explanation: All nodes have the same value, so only the first remains.
Input: [1, 2, 3, 4]
Expected Output: [1, 2, 3, 4]
Explanation: No duplicates exist, so the list is unchanged.
Input: [1, 1, 2, 3, 3, 3, 4, 4, 5]
Expected Output: [1, 2, 3, 4, 5]
Explanation: Repeated adjacent values are removed, leaving one copy of each.
Solution
def solution(values):
class ListNode:
__slots__ = ('val', 'next')
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build_linked_list(vals):
dummy = ListNode()
tail = dummy
for v in vals:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
def to_list(head):
result = []
while head is not None:
result.append(head.val)
head = head.next
return result
head = build_linked_list(values)
current = head
while current is not None and current.next is not None:
if current.val == current.next.val:
current.next = current.next.next
else:
current = current.next
return to_list(head)
Time complexity: O(n). Space complexity: O(1) auxiliary space for the deduplication step (excluding input/output list conversion).
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
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.
Input: ([5, 5, 5, 5], 'hash')
Expected Output: [5]
Explanation: All duplicates are removed except the first occurrence.
Input: ([1, 2, 3, 4], 'runner')
Expected Output: [1, 2, 3, 4]
Explanation: No duplicates exist, so the list is unchanged.
Input: ([3, 1, 2, 3, 1, 4, 2], 'hash')
Expected Output: [3, 1, 2, 4]
Explanation: The first occurrence of each value is kept, and later repeats are removed.
Solution
def solution(values, method='hash'):
class ListNode:
__slots__ = ('val', 'next')
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build_linked_list(vals):
dummy = ListNode()
tail = dummy
for v in vals:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
def to_list(head):
result = []
while head is not None:
result.append(head.val)
head = head.next
return result
head = build_linked_list(values)
if method == 'hash':
if head is None:
return []
seen = {head.val}
current = head
while current.next is not None:
if current.next.val in seen:
current.next = current.next.next
else:
seen.add(current.next.val)
current = current.next
elif method == 'runner':
current = head
while current is not None:
runner = current
while runner.next is not None:
if runner.next.val == current.val:
runner.next = runner.next.next
else:
runner = runner.next
current = current.next
else:
raise ValueError("method must be either 'hash' or 'runner'")
return to_list(head)
Time complexity: If method='hash': O(n) average time. If method='runner': O(n^2) time.. Space complexity: If method='hash': O(n) auxiliary space. If method='runner': O(1) auxiliary space (excluding input/output list conversion)..
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.