Remove Duplicates from Sorted List

描述

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

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

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

分析

无

递归版

  1. // Remove Duplicates from Sorted List
  2. // 递归版，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode *deleteDuplicates(ListNode *head) {
  6.         if (!head) return head;
  7.         ListNode dummy(head->val + 1); // 值只要跟head不同即可
  8.         dummy.next = head;
  10.         recur(&dummy, head);
  11.         return dummy.next;
  12.     }
  13. private:
  14.     static void recur(ListNode *prev, ListNode *cur) {
  15.         if (cur == nullptr) return;
  17.         if (prev->val == cur->val) { // 删除head
  18.             prev->next = cur->next;
  19.             delete cur;
  20.             recur(prev, prev->next);
  21.         } else {
  22.             recur(prev->next, cur->next);
  23.         }
  24.     }
  25. };

迭代版

  1. // Remove Duplicates from Sorted List
  2. // 迭代版，时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode *deleteDuplicates(ListNode *head) {
  6.         if (head == nullptr) return nullptr;
  8.         for (ListNode *prev = head, *cur = head->next; cur != nullptr; cur = prev->next) {
  9.             if (prev->val == cur->val) {
  10.                 prev->next = cur->next;
  11.                 delete cur;
  12.             } else {
  13.                 prev = cur;
  14.             }
  15.         }
  16.         return head;
  17.     }
  18. };

相关题目

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