Remove duplicates in linked list
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Given a linked list, remove all duplicate values so that each value appears only once. Provide solutions for both sorted and unsorted linked lists, along with their time and space complexity analyses.
Quick Answer: This question evaluates proficiency in linked list manipulation, duplicate detection and removal, and algorithmic complexity analysis for both sorted and unsorted data.
You are given the node values of a singly linked list in order as an array values and a boolean is_sorted indicating whether the list is in non-decreasing order. Remove all duplicate values so that each value appears only once. Preserve the original relative order of the first occurrences. Return the resulting array of values.
Constraints
- 0 <= len(values) <= 200000
- Values fit in 32-bit signed integer range
- If is_sorted is True, values is non-decreasing
- Preserve the relative order of first occurrences in the output
- Expected time: O(n); Space: O(1) if is_sorted else O(n)
Hints
- If the list is sorted, compare each value to the last kept value to skip duplicates.
- If the list is unsorted, use a hash set to track seen values and keep only the first occurrence.
- Ensure the output preserves the order of first occurrences.