Remove Duplicates
Write code to remove duplicates from an unsorted linked list.
Solution
The solution is fairly straight forward. We will iterate through the linked list, and keep track of unique values in a separate data structure. When we encounter a duplicate element, we will delete it from the list.
def remove_duplicates(linked_list):
node = linked_list.head
unique_values = []
while node:
if node.value in unique_values:
linked_list.delete(node)
else:
unique_values.append(node.value)
node = node.next
The solution will iterate through the linked list once, so the time complexity is \(O(n)\).