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
