Given the head
of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Example 1:
Input: head = [1,1,2] Output: [1,2]
Example 2:
Input: head = [1,1,2,3,3] Output: [1,2,3]
Constraints:
[0, 300]
.-100 <= Node.val <= 100
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force method for removing duplicates in a sorted list is like checking every single value against every other value. We painstakingly compare each item to all subsequent items to identify and handle duplicates. It's a thorough but inefficient way to solve the problem.
Here's how the algorithm would work step-by-step:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def remove_duplicates_brute_force(head):
current_node = head
while current_node:
# Iterate through the rest of the list for each node.
runner_node = current_node
while runner_node.next:
if current_node.val == runner_node.next.val:
# Remove the duplicate node
runner_node.next = runner_node.next.next
else:
runner_node = runner_node.next
# Advance current_node to the next unique node.
current_node = current_node.next
return head
Since the list is sorted, we can solve this problem efficiently by traversing it only once. We just need to keep track of the last unique element we've seen and remove any subsequent duplicates we encounter.
Here's how the algorithm would work step-by-step:
class ListNode:
def __init__(self, value=0, next_node=None):
self.value = value
self.next = next_node
def remove_duplicates_from_sorted_list(head):
if not head:
return head
current_node = head
while current_node.next:
# Compare current node to the next
if current_node.value == current_node.next.value:
# Remove the duplicate node
current_node.next = current_node.next.next
else:
# Move to the next unique node
current_node = current_node.next
return head
Case | How to Handle |
---|---|
Empty list (head is null) | Return null immediately as there's nothing to process. |
List with only one node | Return the head as is, since there are no duplicates possible. |
List with all nodes having the same value | The algorithm should reduce the list to a single node with that value. |
List with consecutive duplicate values at the beginning | The algorithm should correctly skip all initial duplicates. |
List with consecutive duplicate values in the middle | The algorithm should correctly skip all middle duplicates while maintaining the sorted order. |
List with consecutive duplicate values at the end | The algorithm should correctly remove trailing duplicates and terminate the list properly. |
Large list (potential performance concerns) | The iterative approach maintains O(n) time complexity, which scales linearly, but recursion could lead to stack overflow. |
Negative and positive values intermixed with duplicates | Since the list is sorted, the algorithm handles both negative and positive values equally by comparing adjacent nodes. |