# Remove duplicate copies of a number from unsorted linked list

--

Remove the duplicate copies of number from the unsorted linked list, means only keep the a number 1 time , in the linked list

What if extra space (temporary buffer can’t be used)?

Approach 1:

If temporary buffer can’t be used , then this is solved in O(n²) time and O(1) space. For each of the current node , see if any node succeeding that node , has the same value. And remove all those nodes.

def remove_dup(self,head): curr = head

while(curr):

runner=curr

while(runner.next): if runner.next.data==curr.data:

runner.next=runner.next.next

else:

runner=runner.next curr=curr.next return head

Time : O(n²)

Space: O(1)

Approach 2:

*Using hashmap*

Use the hash set to store the previously visited node

def remove_dup(self,head): curr = head

while(curr):

if curr.data in hash_set:

prev.next=curr.next

else:

hash_set.add(curr.data)

prev=curr

curr=curr.next

return head

Time : O(n)

Space: O(n)