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

解题思路

题意：在一个有序链表中，链表中的值重复的节点仅保留一个。

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

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

方法一：递归，跳过连续相等的元素

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

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 作为头节点的链表做处理，使值相等的节点仅保留一个。然后我们看到 self.deleteDuplicates(head) 函数就是做这个事情的！所以 head.next = self.deleteDuplicates(head.next)，这就是递归调用的由来。
  • 如果 head.val == head.next.val ，说明头节点的值 等于 下一个节点的值，所以当前的 head 节点必须删除，删除到哪个节点为止呢？按照函数定义，我们保留值相等的各个节点中最后一个节点，所以 head 到与 head.val 相等的最后一个节点之间的节点也都需要删除；需要用 move 指针一直向后遍历寻找到最后一个与 head.val 相等的节点。此时 move 之前的节点都不保留了，因此返回 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.next and head.val == move.next.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->next && head->val == move->next->val) {
  12.                 move = move->next;
  13.             }
  14.             return deleteDuplicates(move);
  15.         }
  16.         return head;
  17.     }
  18. };
  • 时间复杂度：$O(N)$，每个节点访问了一次。
  • 空间复杂度：$O(N)$，递归调用的时候会用到了系统的栈。

方法二：递归，删除下一个相等的元素

区别于上面的在递归中一次跳过多个连续相等的元素，下面的递归方法，每次只删除一个节点。

2.1 递归函数定义

与 1.1 相同。

2.2 递归终止条件：

  • 当 head 不存在或者 head.next 不存在，直接返回 head；

    2.3 递归调用

    无论 head.val 和 head.next.val 是否相等，head.next 一定等于后续链表的去重，即 self.deleteDuplicates(head.next) 。原因是：

  • 当 head.val != head.next.val 时，head 节点要保留，所以 head.next = self.deleteDuplicates(head.next) 比较好理解，因为要把后面去重的链表拼接到当前 head 节点之后；

  • 当 head.val == head.next.val 时， head 节点要删除，所以 return head.next ，如果我们不把 head.next = self.deleteDuplicates(head.next)， 那么 return 的结果是原始 head.next ，所以仍然是没去重。

    2.4 返回结果

  • 当 head.val != head.next.val 时， head 节点要保留，所以 return head ;
    - 当 head.val == head.next.val 时， head 节点要删除，所以 return head.next ;
    1. class Solution(object):
    2.   def deleteDuplicates(self, head):
    3.       if not head or not head.next: return head
    4.       head.next = self.deleteDuplicates(head.next)
    5.       return head if head.val != head.next.val else head.next

迭代

迭代法，我写了两种。一个是利用有序链表这个性质的，二是直接使用 set。

方法三：一次遍历

一次遍历的方法比较好想，有两种方法：一种是遇到值相等的节点保留第一个节点；另一种是遇到值相等的节点保留最后一个节点。保留第一个节点的方法更简单，我这里使用保留第一个节点的做法。

使用两个指针 pre 和 cur：pre 节点表示固定一个节点，cur 用于寻找所有跟 pre 值相等的节点。如果 cur.val 等于 pre.val，则删除 cur。在找到不等的 val 之前，pre 不走，只移动 cur。

  1. class Solution(object):
  2.     def deleteDuplicates(self, head):
  3.         if not head: return None
  4.         prev, cur = head, head.next
  5.         while cur:
  6.             if cur.val == prev.val:
  7.                 prev.next = cur.next
  8.             else:
  9.                 prev = cur
  10.             cur = cur.next
  11.         return head
  1. class Solution {
  2. public:
  3.     ListNode* deleteDuplicates(ListNode* head) {
  4.         if (!head || !head->next) return head;
  5.         ListNode* prev = head;
  6.         ListNode* cur = head->next;
  7.         while (cur) {
  8.             if (prev->val == cur->val) {
  9.                 prev->next = cur->next;
  10.             } else {
  11.                 prev = cur;
  12.             }
  13.             cur = cur->next;
  14.         }
  15.         return head;
  16.     }
  17. };
  • 时间复杂度：$O(N)$，对链表每个节点遍历了一次；
  • 空间复杂度：$O(1)$，只使用了常量的空间。

方法四：利用 set 保存出现过的䛾

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

  1. class Solution:
  2.     def deleteDuplicates(self, head):
  3.         if not head or not head.next: return head
  4.         val_set = set()
  5.         val_set.add(head.val)
  6.         root = ListNode(0)
  7.         root.next = head
  8.         while head and head.next:
  9.             if head.next.val in val_set:
  10.                 head.next = head.next.next
  11.             else:
  12.                 head = head.next
  13.                 val_set.add(head.val)
  14.         return root.next
  • 时间复杂度：$O(N)$，对链表遍历了一次；
  • 空间复杂度：$O(N)$，需要使用 set 保存所有出现过的节点值。

刷题心得

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

参考资料：负雪明烛

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

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

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