82-删除排序链表中的重复元素 II(Remove Duplicates from Sorted List II)
发表于：2021-12-03 | 分类： 中等
字数统计: 235 | 阅读时长: 1分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

英文原文

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

 

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

 

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

中文题目

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

 

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

 

提示：

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序排列

通过代码

高赞题解

各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 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 之后所有与 head.val 相等的节点也都需要删除；删除到哪个节点为止呢？需要用 move 指针一直向后遍历寻找到与 head.val 不等的节点。此时 move 之前的节点都不保留了，因此返回 deleteDuplicates(move);

1.4 返回结果

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

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

对链表 1 -> 2 -> 2 -> 3 递归的过程如下。

82.001.jpeg

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

[]
class Solution(object):
    def deleteDuplicates(self, head):
        if not head or not head.next:
            return head
        if head.val != head.next.val:
            head.next = self.deleteDuplicates(head.next)
        else:
            move = head.next
            while move and head.val == move.val:
                move = move.next
            return self.deleteDuplicates(move)
        return head
[]
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        if (head->val != head->next->val) {
            head->next = deleteDuplicates(head->next);
        } else {
            ListNode* move = head->next;
            while (move && head->val == move->val) {
                move = move->next;
            }
            return deleteDuplicates(move);
        }
        return head;
    }
};
  • 时间复杂度：$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。

[]
class Solution(object):
    def deleteDuplicates(self, head):
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        cur = head
        while cur:
            # 跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置
            while cur.next and cur.val == cur.next.val:
                cur = cur.next
            if pre.next == cur:
                 # pre和cur之间没有重复节点，pre后移
                pre = pre.next
            else:
                # pre->next指向cur的下一个位置（相当于跳过了当前的重复元素）
                # 但是pre不移动，仍然指向已经遍历的链表结尾
                pre.next = cur.next
            cur = cur.next
        return dummy.next
[]
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* preHead = new ListNode(0);
        preHead->next = head;
        ListNode* pre = preHead;
        ListNode* cur = head;
        while (cur) {
            //跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置
            while (cur->next && cur->val == cur->next->val) {
                cur = cur->next;
            }
            if (pre->next == cur) {
                //pre和cur之间没有重复节点，pre后移
                pre = pre->next; 
            } else {
                //pre->next指向cur的下一个位置（相当于跳过了当前的重复元素）
                //但是pre不移动，仍然指向已经遍历的链表结尾
                pre->next = cur->next;
            }
            cur = cur->next;
        }
        return preHead->next;
    }
};
  • 时间复杂度：$O(N)$，对链表每个节点遍历了一次；
  • 空间复杂度：$O(1)$，只使用了常量的空间。

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

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

[]
class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(0)
        dummy.next = head
        val_list = []
        while head:
            val_list.append(head.val)
            head = head.next
        counter = collections.Counter(val_list)
        head = dummy
        while head and head.next:
            if counter[head.next.val] != 1:
                head.next = head.next.next
            else:
                head = head.next
        return dummy.next
[]
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        unordered_map<int, int> m;
        ListNode dummy(0);
        ListNode* dummy_move = &dummy;
        ListNode* move = head;
        while (move) {
            m[move->val]++;
            move = move->next;
        }
        move = head;
        while (move) {
            if (m[move->val] == 1) {
                dummy_move->next = move;
                dummy_move = dummy_move->next;
            }
            move = move->next;
        }
        dummy_move->next = nullptr;
        return dummy.next;
    }
};
  • 时间复杂度：$O(N)$，对链表遍历了两次；
  • 空间复杂度：$O(N)$，需要一个字典保存每个节点值出现的次数。

刷题心得

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

参考资料：负雪明烛

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

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

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

统计信息

通过次数 提交次数 AC比率
197853 372595 53.1%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
删除排序链表中的重复元素 简单
双指针 链表
上一篇:
80-删除有序数组中的重复项 II(Remove Duplicates from Sorted Array II)
下一篇:
83-删除排序链表中的重复元素(Remove Duplicates from Sorted List)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo