Remove duplicate from unsorted linked list

METHOD 1 (Using two loops)

struct node
{
 int data;
 struct node *next;
};
 
void removeDuplicates(struct node *start)
{
  struct node *ptr1, *ptr2, *dup;
  ptr1 = start;
 
  while(ptr1 != NULL && ptr1->next != NULL)
  {
     ptr2 = ptr1;
 
     while(ptr2->next != NULL)
     {
       if(ptr1->data == ptr2->next->data)
       {
          dup = ptr2->next;
          ptr2->next = ptr2->next->next;
          free(dup);
       }
       else 
       {
          ptr2 = ptr2->next;
       }
     }
     ptr1 = ptr1->next;
  }
}

Time Complexity: O(n^2)

METHOD 2 (Use Sorting)

In general, Merge Sort is the best suited sorting algorithm for sorting linked lists efficiently.
1) Sort the elements using Merge Sort. O(nLogn)
2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List. O(n)

Please note that this method doesn’t preserve the original order of elements.

Time Complexity: O(nLogn)

METHOD 3 (Use Hashing)

void deleteDups(LinkedListNode n)
{
    Hashtable table = new Hashtable();
    LinkedListNode previous = null;
    while (n != null) {
        if (table.containsKey(n.data)) 
            previous.next = n.next;                   
        else {
            table.put(n.data, true);
            previous = n;
        } 
        n = n.next;
    }
}

Time Complexity: O(n) on average