Try   HackMD

82. Remove Duplicates from Sorted List II


My Solution

The Key Idea for Solving This Coding Question

C++ Code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode *deleteDuplicates(ListNode *head) { if (head == nullptr || head->next == nullptr) { return head; } // At least, we have two nodes in the linked list. ListNode *dummy = new ListNode(); ListNode *prev = dummy, *left = head, *right = head; dummy->next = head; while (right != nullptr) { if (left->val == right->val) { right = right->next; continue; } if (left->next == right) { right = right->next; left = left->next; prev = prev->next; continue; } deleteNodes(prev, left, right); left = right; } if (left->next != right) { deleteNodes(prev, left, right); } head = dummy->next; delete dummy; return head; } private: void deleteNodes(ListNode *prev, ListNode *left, ListNode *right) { prev->next = right; while (left != right) { ListNode *x = left; left = left->next; delete x; } } };

Time Complexity

O(n)
n
is the number of nodes in the linked list referred by head.

Space Complexity

O(1)

C++ Code 2

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode *dummy = new ListNode(-200, head), *prev = dummy, *curr = head; while (curr && curr->next) { if (curr->val == curr->next->val) { curr = curr->next; continue; } if (prev->next == curr) { prev = prev->next; curr = curr->next; } else { curr = curr->next; deleteDuplicates(prev, curr); } } if (prev->next != curr) { curr = curr->next; deleteDuplicates(prev, curr); } head = dummy->next; delete dummy; return head; } private: void deleteDuplicates(ListNode *left, ListNode *right) { while (left->next != right) { ListNode *x = left->next; left->next = x->next; delete x; } } };

Miscellaneous