Given the head of a sorted doubly linked list,\u00a0remove all duplicate nodes from the list. Each node should appear\u00a0only once in the final list.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Example 1:<\/strong><\/p>\n\n\n\n Example 2:<\/strong><\/p>\n\n\n\n Your Task:<\/strong> Constraint:<\/strong> Think of this like organizing a bookshelf where books are arranged alphabetically, but you have multiple copies of some books! Since the books are already sorted, all duplicate copies will be sitting right next to each other. You can simply walk through the shelf and whenever you see two identical books next to each other, remove one of them. In a doubly linked list, we do the same – traverse the list and remove duplicate nodes that are adjacent to each other.<\/p>\n\n\n\nInput:
<\/strong>n = 6
<\/strong>1<->1<->1<->2<->3<->4
Output:
<\/strong>1<->2<->3<->4
Explanation:<\/strong>
Only the first occurance of node with value 1 is
retained, rest nodes with value = 1 are deleted.<\/pre>\n\n\n\nInput:\n<\/strong>n = 7\n<\/strong>1<->2<->2<->3<->3<->4<->4\nOutput:\n<\/strong>1<->2<->3<->4\nExplanation:<\/strong>\nOnly the first occurance of nodes with values 2,3 and 4 are \nretained, rest repeating nodes are deleted.<\/pre>\n\n\n\n
You have to complete the method removeDuplicates<\/strong>() which takes 1<\/strong> argument: the head<\/strong> of the linked list. Your function should return a pointer to a linked list with no duplicate element.<\/p>\n\n\n\n
1 <= n <= 105<\/sup>
Expected Time Complexity: <\/strong>O(n)
Expected Space Complexity: <\/strong>O(1)<\/p>\n\n\n
\n\n\n\nSolution: Optimal Approach (Single Pass Traversal)<\/h2>\n\n\n\n
Intuition<\/h3>\n\n\n\n
Detailed Approach<\/h3>\n\n\n\n
\n
Code<\/h3>\n\n\n\n