a Write a pseudo code for an algorithm that removes all dupl

a) Write a pseudo code for an algorithm that removes all duplicated numbers given a list of unsorted integers.

b)Analyze the worst-case time complexity of your algorithm in (1) using big-O notation, show steps.

Solution

Hi, Please find my algorithm:

We traverse the link list from head to end. For every newly encountered element, we check whether it is in the hash table: if yes, we remove it; otherwise we put it in the hash table.

Thanks to bearwang for suggesting this method.

Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).

PSUDO CODE

removeDuplicate(LinkedList head){
  
   // creating a HashSet
   HashSet set

   // traversing through all nodes and if it is notin HashSet then adding both in HashSet and linked list

   Node temp = head
   set.add(temp)// adding first node in set
   while(temp.next != null){

       if(set.contains(temp.next))
           temp.next = temp.next.next; // skipping this node because it has already seen in list earlier
       else{
           // adding in set
           set.add(temp.next);
           // forwarding temp to next node
           temp = temp.next;

       }
   }
}