Given a sorted linked list, delete all nodes that have duplicate numbers (all occurrences), leaving only numbers that appear once in the original list, and return the head of the modified linked list.
Examples:
Input: Linked List = 23->28->28->35->49->49->53->53 Output: 23 35 Explanation:
The duplicate numbers are 28, 49 and 53 which are removed from the list.
Input: Linked List = 11->11->11->11->75->75 Output: Empty list Explanation:
All the nodes in the linked list have duplicates. Hence the resultant list would be empty.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
Constraints:
1 ≤ size(list) ≤ 105
Approach 01:
-
C++
-
Python
class Solution {
public:
Node* removeAllDuplicates(Node* head) {
Node* temp = new Node(0);
temp->next = head;
Node* prev = temp;
Node* curr = head;
while (curr) {
while (curr->next && curr->data == curr->next->data) {
curr = curr->next;
}
if (prev->next == curr) {
prev = prev->next;
}
else {
prev->next = curr->next;
}
curr = curr->next;
}
return temp->next;
}
};
class Solution:
def removeAllDuplicates(self, head):
temp = Node(0)
temp.next = head
prev= temp
curr = head
while(curr):
while(curr.next and curr.data == curr.next.data):
curr = curr.next
if prev.next == curr:
prev = prev.next
else:
prev.next = curr.next
curr = curr.next
return temp.next