Make delicious recipes!

Remove duplicates in a linked list

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.

This is somewhat similar to the Sieve of Eratosthenes for finding primes.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal