You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Remove Duplicates In List

Nicholas Wong
Nicholas Wong

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

Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.