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)\).