Remove duplicate copies of a number from unsorted linked list
Sep 23, 2021
--
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)
