Remove Duplicates

Question#

Given the head node of a singly linked list, remove all duplicate elements.

Approach#

To remove the duplicates, we will need to iterate through the entire linked list and keep track of the elements we come across. If we have already encountered an element before, we then remove it from the linked list.

Implementation#

def remove_duplicates(head):
curr = head
prev = None
duplicates = {}
while curr:
if curr.data in duplicates:
# remove node
prev.next = curr.next
curr = None
else:
duplicates[curr.data] = 1
prev = curr
curr = prev.next

Analysis#

  • Time complexity: O(n) where n is the length of linked list
  • Space complexity: O(n) where n is number of elements in linked list