Remove duplicates from an unsorted linked list

Problem description :

Write a method to remove duplicates from an unsorted linked list.

Input : A linked list
Output : A linked list with unique elements

This post is a follow-up of JavaScript Linked List Example. I recommend reading that first, as the following code uses the method from it.


Approach 1: If you are allowed to use any additional data structure to store the values.

Time complexity : O (n)

Logic :

  • Iterate through linked list adding each node to the hash table (JSON).
  • When the duplicate element is found, remove it from the linked list and update the linked list.

Solution :


Approach 2: If you are not allowed to use any additional data structure to store the values.

Time complexity : O (n^2)

Logic :

  • Iterate through linked list getting one node at a time
    • Iterate through the rest of the linked list and compare the current node’s value
    • When duplicate element is found, remove it from the linked list and update the linked list.

Solution :

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

Show Buttons
Hide Buttons