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;
 }
}

• zdd: It seems your method only remove the adjacent duplicate elements. is that the case?
• Phoenix: no i don't intend for it to be that way. Every node is being compared to every NEXT LL node up to the end of the list.
• Phoenix: Can you cite some examples of what you are saying
• zdd: OK, take an unsorted list for example, 1->1->2->1->3->2->2->3, you code want to get a result of 1->2->3, right?
• zdd: I think I understand your code now, you are right! but I have another version with a little difference, we can save a pointer, please see my answer.

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.

• Phoenix: Frank thank you for the comments. I skipped writing the equals method but it is intended to compare node equality of data. You mention sorting linked lists. Will it be a merge sort for linked lists ?
• Frank: Yes, you would probably use a merge sort, as it suits the linked list nicely. Ideally, you could simply use Collections.sort, but that makes a copy, which requires linear memory.

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.