Remove Duplicates from Sorted List II

描述

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,

Given 1->2->3->3->4->4->5, return 1->2->5.

Given 1->1->1->2->3, return 2->3.

分析

无

递归版

  1. // Remove Duplicates from Sorted List II
  2. // 递归版，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode *deleteDuplicates(ListNode *head) {
  6.         if (head == nullptr || head->next == nullptr) return head;
  8.         ListNode *p = head->next;
  9.         if (head->val == p->val) {
  10.             while (p != nullptr && head->val == p->val) {
  11.                 ListNode *tmp = p;
  12.                 p = p->next;
  13.                 delete tmp;
  14.             }
  15.             delete head;
  16.             return deleteDuplicates(p);
  17.         } else {
  18.             head->next = deleteDuplicates(head->next);
  19.             return head;
  20.         }
  21.     }
  22. };

迭代版

  1. // Remove Duplicates from Sorted List II
  2. // 迭代版，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode *deleteDuplicates(ListNode *head) {
  6.         if (head == nullptr) return head;
  8.         ListNode dummy(INT_MIN); // 头结点
  9.         dummy.next = head;
  10.         ListNode *prev = &dummy, *cur = head;
  11.         while (cur != nullptr) {
  12.             bool duplicated = false;
  13.             while (cur->next != nullptr && cur->val == cur->next->val) {
  14.                 duplicated = true;
  15.                 ListNode *temp = cur;
  16.                 cur = cur->next;
  17.                 delete temp;
  18.             }
  19.             if (duplicated) { // 删除重复的最后一个元素
  20.                 ListNode *temp = cur;
  21.                 cur = cur->next;
  22.                 delete temp;
  23.                 continue;
  24.             }
  25.             prev->next = cur;
  26.             prev = prev->next;
  27.             cur = cur->next;
  28.         }
  29.         prev->next = cur;
  30.         return dummy.next;
  31.     }
  32. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/linear-list/linked-list/remove-duplicates-from-sorted-list-ii.html