This post is completed by 1 user

  • 0
Add to List
Beginner

27. Remove Duplicates from an Unsorted Linked list

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

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 an option to check every node data against every other node data and if find duplicates, delete that node.
Time Complexity: O(n^2)

Output:

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