Given the reference (pointer) to the head node of a linked list, the task is to remove duplicates from it.
Input: 5->2->2->4->null
Output: 5->2->4->null
Input: 1->2->2->3->2->null
Output: 1->2->3->null
Solutions
Method 1: Using Hashing - O(n) time and O(n) space
The idea is to traverse the list and store the node's references in a "Hash", also maintain "previous" node's refereence for every current node.
In each iteration, check if the current node's reference is already present in the "Hash". If yes, delete the current node and do not asiign current to prev.
To delete a node, point 'prev' to the current's next.
Complexity
The time complexity of this solution is O(n) and space complexity is also O(n).