Try   HackMD

83. Remove Duplicates from Sorted List


My Solution

The Key Idea for Solving This Coding Question

C++ Code

class Solution { public: ListNode *deleteDuplicates(ListNode *head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode *prev = head, *curr = head->next; while (curr != nullptr) { if (curr->val == prev->val) { // Find a duplicate. ListNode *x = curr; prev->next = curr->next; curr = curr->next; delete x; } else { curr = curr->next; prev = prev->next; } } return head; } };

Time Complexity

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

Space Complexity

O(1)

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) { 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 { while (prev->next != curr) { ListNode *x = prev->next; prev->next = x->next; delete x; } } } while (prev->next != curr) { ListNode *y = prev->next; prev->next = y->next; delete y; } head = dummy->next; delete dummy; return head; } };

Miscellaneous