Objective: Write a program to remove the duplicates from an unsorted linked list

Example:

Input Linked List : 1->2->2->4->3->3->2
Output : 1->2->4->3

Input: An unsorted linked list

Output: Linked list with no duplicates.

Approach:

Create a Hash Map

Take two pointers, prevNode and CurrNode.

PrevNode will point to the head of the linked list and currNode will point to the head.next.

Now navigate through the linked list.

Check every node data is present in the Hash Map.

if yes then delete that node using prevNode and currNode.

If No, then insert that node data into the Hash Map.

Return the head of the list

Time Complexity : O(n)
Space Complexity : O(n)

Follow Up: If suppose addition buffer is not allowed then we have option but to check every node data against every other node data and if find duplicates, delete that node. Time Complexity : O(n^2)

Complete Code for the Hash Table method:

Output:

Original List : ->1->2->2->3->4->4->2
Updated List: ->1->2->3->4

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________