Remove duplicates in a linked list - PrismoSkills
It is pretty easy if additional memory is allowed.Just allocate a hash-set, store the entries there and remove nodes if they are duplicates.
If no extra memory is allowed, then O(n2) solution has to be used.
However, that solution can be improvised a little.
When iterating, do not remove duplicates of the current element in the list already traversed.
Rather, remove duplicates in the list still not traversed.
In other words, do not traverse back to remove duplicates, rather traverse forwards.
This is useful when say a single node has many duplicates.
By traversing forwards, all those duplicates will be removed in one go.
Where as, if we traverse backwards, each duplicate removal will be truly O(k-1) making the whole algorithm truly O(n2)
The forward algorithm is also O(n2) in the worst case, but it will give good results when number of duplicates is high.
Read full article from Remove duplicates in a linked list - PrismoSkills
