Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
Solution I: (Using HashSet)
classSolution{public:ListNode*deleteDuplicates(ListNode*head) {if(head ==NULL){return head;} unordered_set<int> s; ListNode *p =head->next; ListNode *q = head;while (p !=NULL) {if (p->val ==q->val) {s.insert(p->val);q->next =p->next; p =p->next; }else { q =q->next; p =p->next; } } p = head; q =NULL;while (p !=NULL) {if (s.find(p->val) !=s.end()) {if (q !=NULL) {q->next =p->next; p =p->next; }elseif(q ==NULL) { head =p->next; p = head; } }else { q = p; p =p->next; } }return head; }};
Time Complexity: O(n) , Space Complexity: O(n)
Solution II:
classSolution{public:ListNode*deleteDuplicates(ListNode*head) {if (head ==NULL) {return head; } // Creating a Dummy node to check duplicates in head ListNode* temp =new ListNode;temp->next = head; ListNode *p = head; ListNode *q = temp;while (p!=NULL) {while (p->next &&p->val ==p->next->val) { p =p->next; }if (q->next == p) { q = p; }else {q->next =p->next; } p =p->next; } //Pointing to dummy of next head =temp->next;return head; }};