力扣刷题TOP101：14.BM16 删除有序链表中重复的元素-II

目录：

目的

思路

复杂度

记忆秘诀

python代码

目的

1→1→2→3→3 删除重复后变成2。

---

思路

这个任务是删除链表里重复的节点包含本身。可以看成是一个抽奖活动的系统升级。某人通过多种方式报名（节点不同），后台数据检测到这些人其实是同一个人（节点值相同）。为了公平抽奖并且惩罚该人，系统删除该用户的所有报名记录（所有重复节点），只保留那些唯一的报名用户。

---

准备检查：

• 创建了一个临时记录dummy：
  设置一个临时记录，方便从头开始管理，避免对第一个报名者的特殊处理。dummy.next = head 表示临时记录指向实际第一个用户节点。
• 系统管理员prev：
  负责指引哪些记录有效，哪些需要删除。在开始时，prev 指向临时记录 dummy，准备去处理实际用户。
• 正在被检查的用户current：
  系统正在检查的报名信息，逐一遍历，确保没有重复的报名。

---

开始检查：

• 系统检查当前记录点和下一个记录是否重复：
  如果发现当前记录和下一个记录重复（ if current.next and current.val == current.next.val:），系统就开始一个内循环（while current.next and current.val == current.next.val:），继续跳过所有重复的报名记录（current = current.next），直到所有相同的记录都被跳过。比如，某个用户通过不同方式多次报名，系统会一直跳过他们，直到没有更多重复记录为止。
• 管理员操作：
  • 有重复的情况：
    当我们跳过了所有重复的记录后，系统管理员会删除当前重复的所有记录（prev.next = current.next）。具体操作是让 prev（即最后一个不重复的报名记录）指向 current 后面唯一的一个不重复的记录，也就是跳过所有重复的报名记录。
  • 没有重复的情况：
    管理员会把继续准备检查下一条记录prev = prev.next。
• 系统继续检查下一个用户：
  无论当前记录是否重复，系统都会继续检查下一个记录current = current.next。

---

检查结束：

从第一个报名记录开始检查，一直检查到所有记录都处理完为止。最后，系统返回去掉所有重复报名记录后的链表，dummy.next 就是去除重复节点后的实际链表头。

---

复杂度

• 时间复杂度：O(n）

  • 只检查了一次报名表，链表被遍历一次，n 是链表中节点的数量。

• 空间复杂度：O(1)

  • 只使用了常数级别的额外空间。

---

记忆秘诀

• 虚拟头节点：避免处理链表头部的特殊情况。
• 内外循环配合：内循环跳过重复节点，外循环更新链表。
• 返回结果：返回去重后的实际链表dummy.next。

---

python代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:def deleteDuplicates(self, head: ListNode) -> ListNode:# 创建一个虚拟头节点，方便处理边界情况dummy = ListNode(0)dummy.next = headprev = dummy  # prev指向当前不重复元素的前一个节点current = head  # current指向当前节点while current:# 检查当前节点是否有重复if current.next and current.val == current.next.val:# 找到所有重复的节点while current.next and current.val == current.next.val:current = current.next  # 跳过重复节点# 将prev的下一个指向当前节点的下一个，即删除重复节点prev.next = current.nextelse:# 如果没有重复，prev指向当前节点prev = prev.next# 移动到下一个节点current = current.nextreturn dummy.next  # 返回去掉重复元素后的链表头节点

---

* 欢迎大家探讨新思路，能够更好的理解和记忆