Remove Duplicates In List

Remove Duplicates In List

Question

Write an algorithm to remove duplicated node from a linked list.

Solution with O(n²)

There are many ways to do it. For the first one, as the simplest one, we could use 2 loops to compare each element with all other elements. However, this takes forever: O(n²).

Solution with O(n log n)

Sort the list with merge sort, and then check the list one by one, if the current one is the same as the previous one, don't have the output that element.

Solution with O(n)

Simple, go through the list once and put each item in a tree map. Then go through the list once again and only output each element once.

Reference