[Java] Remove duplicates from a singly LinkedList

Here is a simple method to remove all duplicate nodes from a singly LinkedList (not the standard one) without using additional data structures. This means the runtime is going to be O(N^2) and space is going to be O(1).

The idea is simply to walk the list with a pointer and for each element walk the remainder of the list using two pointers. When we find a match to the element we are currently evaluating, we remove it. It is not possible to remove the head element, so we can edit the list in place.

You can check my Gist for the code with tests (RemoveDuplicates) and the LinkedList data structure (SingleLinkedListNode):

 public static void removeDuplicates(SingleLinkedListNode head){  
     SingleLinkedListNode curr, prev, next;  
   
     curr = head;  
   
     //for each single node  
     while(curr != null){  
       //track 2 nodes at the same time  
       prev = curr;  
       next = prev.next;  
       //walk the whole list  
       while(next != null){  
         /*  
         if the next node is a duplicate, delete it by linking the previous to the next.next  
         CAUTION: do NOT move the previous node because we could lose a value  
         */  
         if(next.data == curr.data) prev.next = next.next;  
         //only move previous if the next one was unique  
         else prev = prev.next;  
         //move next to the new next element  
         if(prev != null) next = prev.next;  
       }  
       curr = curr.next;  
     }  
   }