Removing duplicates from an unsorted linked list

Question

Does the code below look correct and efficient for removing duplicates from an unsorted linked list without using extra memory?

An object of type Node denotes a LL node.

void removeDuplicates()
{
  Node current = head; 
  while(current!=null)
  {
    Node prev = current;
    Node next = current.next;
    while(next!=null)
    {
      if(current.equals(next))
      {
         prev.next = next.next;
      }
      else
      {
         prev = next;
      }
      next = next.next;
    }
      current = current.next;
   }
}

Answer 1

This review is two-fold: once, in case you have to uphold your restriction and then what changes if you allow extra space.

Review

• Comments: they are simply missing. You need at least some javadoc, and for non-trivial methods like this some more never hurts. Oh, and skip the usual excuses about how this code is somehow special and doesn't need comments.

• Clarity and Intent: if (current.equals(head)) reads like you are comparing the actual nodes, while duplicity is a matter of equal node values. You may have overwritten the equals method accordingly (I assume so for the sake of correctness), but I would prefer to clearly portray your original intent here by comparing the actual values.

• Efficiency and readability: As the answer by zdd points out you could save one pointer, but that's kind of pointless. I prefer your version as its much clearer to a reader what current, prev and next are. However,efficiency is not going to get below O(n^2) with this approach.

Efficiency Improvement

You said that you need a solution "without using extra memory". What you really meant of course is a solution "with only a constant amount of additional memory" (your pointers require memory as well after all). What you did not require, however, is that this operation has to leave the list elements' ordering intact. Therefore, a faster approach in O(n log(n)) would be to first sort the list (in-place to satisfy the memory requirement), then simply walk through the list comparing only neighbors (another O(n)). While this does not make much difference of course for smaller lists, the memory requirement indicates much larger lists, and then the difference between O(n^2) and O(n log(n)) may well be the difference between another problem and a solution.

Answer 2

If you use Java, you can use contains method.

Then, if you replace ArrayList by LinkedList in the code here, and forget decoration, you can remove duplicate.

Using a temporary additinional List simplify the complexity.