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.