{"id":5665,"date":"2019-09-30T23:14:56","date_gmt":"2019-10-01T06:14:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5665"},"modified":"2019-09-30T23:15:46","modified_gmt":"2019-10-01T06:15:46","slug":"leetcode-82-remove-duplicates-from-sorted-list-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-82-remove-duplicates-from-sorted-list-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 82. Remove Duplicates from Sorted List II"},"content":{"rendered":"\n

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct<\/em> numbers from the original list.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> 1->2->3->3->4->4->5\nOutput:<\/strong> 1->2->5\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> 1->1->1->2->3\nOutput:<\/strong> 2->3<\/pre>\n\n\n\n
Solution:<\/strong><\/h2>\n\n\n\n
Time complexity: O(n)
Space complexity: O(1)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  ListNode *deleteDuplicates(ListNode *head) {\n    if (!head) return nullptr;\n    ListNode dummy = ListNode(0);\n    ListNode *p = &dummy;\n    while (head) {\n      int c = 0;\n      while (head->next && head->next->val == head->val) {\n        head = head->next;\n        c++;\n      }\n      if (c == 0)\n        p = p->next = head;        \n      else\n        p->next = nullptr;      \n      head = head->next;\n    }\n    return dummy.next;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
Related Problems<\/strong><\/h2>\n\n\n\n