各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 60 天。今天力扣上的每日一题是「82. 删除排序链表中的重复元素 II」。

解题思路

题意：在一个有序链表中，如果一个节点的值出现不止一次，那么把这个节点删除掉。

重点：有序链表，所以，一个节点的值出现不止一次，那么它们必相邻。

下面使用两种方法 ：递归，迭代。其中迭代又分为两种方法。

方法一：递归

链表和树的问题，一般都可以有递归和迭代两种写法。对于本题一定记住是有序链表，值相同的节点会在一起。

1.1 递归函数定义

递归最基本的是要明白递归函数的定义！我反复强调过这一点。

递归函数直接使用题目给出的函数 deleteDuplicates(head) ，它的含义是 删除以 head 作为开头的有序链表中，值出现重复的节点。

1.2 递归终止条件

终止条件就是能想到的基本的、不用继续递归处理的case。
- 如果 head 为空，那么肯定没有值出现重复的节点，直接返回 head；
- 如果 head.next 为空，那么说明链表中只有一个节点，也没有值出现重复的节点，也直接返回 head。

1.3 递归调用

什么时候需要递归呢？我们想一下这两种情况：

  • 如果 head.val != head.next.val ，说明头节点的值不等于下一个节点的值，所以当前的 head 节点必须保留；但是 head.next 节点要不要保留呢？我们还不知道，需要对 head.next 进行递归，即对 head.next 作为头节点的链表，去除值重复的节点。所以 head.next = self.deleteDuplicates(head.next).
  • 如果 head.val == head.next.val ，说明头节点的值等于下一个节点的值，所以当前的 head 节点必须删除；但是 head.next 节点要不要删除呢？我们还不知道，需要一直向后遍历寻找到与 head.val 不等的节点。与 head.val 相等的这一段链表都要删除，因此返回 deleteDuplicates(move);

1.4 返回结果

题目让我们返回删除了值重复的节点后剩余的链表，结合上面两种递归调用的情况。

  • 如果 head.val != head.next.val ，头结点需要保留，因此返回的是 head；
    - 如果 head.val == head.next.val ，头结点需要删除，需要返回的是deleteDuplicates(move);。

所以我们得到以下的代码：

  1. class Solution(object):
  2.     def deleteDuplicates(self, head):
  3.         if not head or not head.next:
  4.             return head
  5.         if head.val != head.next.val:
  6.             head.next = self.deleteDuplicates(head.next)
  7.         else:
  8.             move = head.next
  9.             while move and head.val == move.val:
  10.                 move = move.next
  11.             return self.deleteDuplicates(move)
  12.         return head
  1. class Solution {
  2. public:
  3.     ListNode* deleteDuplicates(ListNode* head) {
  4.         if (!head || !head->next) {
  5.             return head;
  6.         }
  7.         if (head->val != head->next->val) {
  8.             head->next = deleteDuplicates(head->next);
  9.         } else {
  10.             ListNode* move = head->next;
  11.             while (move && head->val == move->val) {
  12.                 move = move->next;
  13.             }
  14.             return deleteDuplicates(move);
  15.         }
  16.         return head;
  17.     }
  18. };
  • 时间复杂度：$O(N)$，每个节点访问了一次。
  • 空间复杂度：$O(N)$，递归调用的时候会用到了系统的栈。

迭代

迭代法，我写了两种。一个是利用有序链表这个性质的，二是直接计数统计出现次数的。

方法二：一次遍历

这里说的一次遍历，是说一边遍历、一边统计相邻节点的值是否相等，如果值相等就删除。

其实思路很简单，跟递归方法中的 while 语句跳过所有值相等的节点的思路是一样的：如果 cur.val == cur.next.val 说明两个相邻的节点值相等，所以继续后移，一直找到 cur.val != cur.next.val ，此时的 cur.next 就是值不等的节点。

比如： 1 -> 2 -> 2 -> 2 -> 3，我们用一个 pre 指向 1；当 cur 指向第一个 2 的时候，发现 cur.val == cur.next.val ，所以出现了值重复的节点啊，所以 cur 一直后移到最后一个 2 的时候，发现 cur.val != cur.next.val ，此时 cur.next = 3 ，所以 pre.next = cur.next ，即让1 的 next 节点是 3，就把中间的所有 2 都删除了。

代码中用到了一个常用的技巧：dummy 节点，也叫做 哑节点。它在链表的迭代写法中非常常见，因为对于本题而言，我们可能会删除头结点 head，为了维护一个不变的头节点，所以我们添加了 dummy，让dummy.next = head，这样即使 head 被删了，那么会操作 dummy.next 指向新的链表头部，所以最终返回的也是 dummy.next。

  1. class Solution(object):
  2.     def deleteDuplicates(self, head):
  3.         if not head or not head.next:
  4.             return head
  5.         dummy = ListNode(0)
  6.         dummy.next = head
  7.         pre = dummy
  8.         cur = head
  9.         while cur:
  10.             while cur.next and cur.val == cur.next.val:
  11.                 cur = cur.next
  12.             if pre.next == cur:
  13.                 pre = pre.next
  14.             else:
  15.                 pre.next = cur.next
  16.             cur = cur.next
  17.         return dummy.next
  1. class Solution {
  2. public:
  3.     ListNode* deleteDuplicates(ListNode* head) {
  4.         if (!head || !head->next) return head;
  5.         ListNode* preHead = new ListNode(0);
  6.         preHead->next = head;
  7.         ListNode* pre = preHead;
  8.         ListNode* cur = head;
  9.         while (cur) {
  10.             //跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置
  11.             while (cur->next && cur->val == cur->next->val) {
  12.                 cur = cur->next;
  13.             }
  14.             if (pre->next == cur) {
  15.                 //pre和cur之间没有重复节点，pre后移
  16.                 pre = pre->next; 
  17.             } else {
  18.                 //pre->next指向cur的下一个位置（相当于跳过了当前的重复元素）
  19.                 //但是pre不移动，仍然指向之前的链表结尾
  20.                 pre->next = cur->next;
  21.             }
  22.             cur = cur->next;
  23.         }
  24.         return preHead->next;
  25.     }
  26. };
  • 时间复杂度：$O(N)$，对链表每个节点遍历了一次；
  • 空间复杂度：$O(1)$，只使用了常量的空间。

方法三：利用计数，两次遍历

这个做法忽略了链表有序这个性质，使用了两次遍历，第一次遍历统计每个节点的值出现的次数，第二次遍历的时候，如果发现 head.next 的 val 出现次数不是 1 次，则需要删除 head.next。

  1. class Solution:
  2.     def deleteDuplicates(self, head):
  3.         dummy = ListNode(0)
  4.         dummy.next = head
  5.         val_list = []
  6.         while head:
  7.             val_list.append(head.val)
  8.             head = head.next
  9.         counter = collections.Counter(val_list)
  10.         head = dummy
  11.         while head and head.next:
  12.             if counter[head.next.val] != 1:
  13.                 head.next = head.next.next
  14.             else:
  15.                 head = head.next
  16.         return dummy.next
  1. class Solution {
  2. public:
  3.     ListNode* deleteDuplicates(ListNode* head) {
  4.         unordered_map<int, int> m;
  5.         ListNode dummy(0);
  6.         ListNode* dummy_move = &dummy;
  7.         ListNode* move = head;
  8.         while (move) {
  9.             m[move->val]++;
  10.             move = move->next;
  11.         }
  12.         move = head;
  13.         while (move) {
  14.             if (m[move->val] == 1) {
  15.                 dummy_move->next = move;
  16.                 dummy_move = dummy_move->next;
  17.             }
  18.             move = move->next;
  19.         }
  20.         dummy_move->next = nullptr;
  21.         return dummy.next;
  22.     }
  23. };
  • 时间复杂度：$O(N)$，对链表遍历了两次；
  • 空间复杂度：$O(N)$，需要一个字典保存每个节点值出现的次数。

刷题心得

  • 今天这个题目挺经典的，非常适合面试。类似的还有删除链表的指定区间。
    - 链表的题目主要是指针移动的次数比较烦，可以在纸上画一画，来理清思路。

参考资料：负雪明烛

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！