Given the reference (pointer) to the head node of a "sorted" linked list, the task is to remove duplicates from it.
Input: 1->2->2->3->4->null
Output: 1->2->3->4->null
Input: 1->2->2->3->null
Output: 1->2->3->null
Solutions
Method 1: In O(n) time and O(1) space
The idea is to traverse the list and keep track of "current" and "previous" node's refereence.
In each iteration, check if the current node's data is equal to previous node's data. If yes, delete the current node.
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 O(1).