【小白笔记】删除排序链表中的重复元素（I 和II）

这道题充分利用了链表便于删除节点的特性，以及题目给出的**“已排序”**这个关键前提。

1. 解题思路：一次遍历

由于链表是已排序的，所有重复的元素在物理位置上一定是相邻的。

1. 初始化：让一个指针cur指向head。
2. 比较与去重：
   • 比较cur和cur.next的值。
   • 如果相等：说明遇到了重复元素。我们只需要让cur.next = cur.next.next，相当于直接把中间那个重复的节点“跳过”了（这就是链表删除节点的高效之处）。
   • 如果不相等：说明当前节点是唯一的，将cur向后移动一位。
3. 循环终止：当cur或cur.next为空时，说明遍历结束。

2. 代码实现 (Python)

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defdeleteDuplicates(self,head:Optional[ListNode])->Optional[ListNode]:# 如果链表为空或只有一个节点，直接返回ifnothead:returnhead cur=head# 只要当前节点和下一个节点都存在，就继续比较whilecurandcur.next:ifcur.val==cur.next.val:# 发现重复，删除 next 节点# 直接指向下下个节点cur.next=cur.next.nextelse:# 不重复，cur 指针后移cur=cur.nextreturnhead

3. 深度解析：为什么这题不需要dummy节点？

在上一题（反转链表 II）中，由于头节点可能会被反转/改变，我们需要dummy。
但在本题中：

• 头节点永远不会被删除。即使后面有和头节点值一样的元素，被删除的也是“后来的”重复项，第一个节点始终会被保留。
• 既然头节点固定，我们直接返回head即可，不需要额外的虚拟节点。

4. 复杂度分析

• 时间复杂度：O(N)O(N)O(N)。我们只对链表进行了一次完整的线性扫描。
• 空间复杂度：O(1)O(1)O(1)。只使用了一个cur指针，没有开辟额外空间。

规则变了：只要一个数字重复出现过，它的所有副本都要被删除。例如：1 -> 2 -> 2 -> 3变成1 -> 3（中间的2全部消失）。

1. 核心突破：为什么要用dummy节点？

在这道题中，dummy节点是必须的。
原因在于：头节点可能会被删除。
例如链表是1 -> 1 -> 2，因为1是重复的，它必须被删掉。如果没有dummy，你很难处理“谁来当新的头”这个问题。有了dummy，我们只需要最后返回dummy.next。

2. 解题思路：三步走

1. 设置哨兵：创建dummy指向head，令pre指向dummy。pre的作用是始终指向“确定不重复的最后一个节点”。
2. 寻找重复区间：让cur指向pre.next。如果发现cur.val == cur.next.val，说明我们进入了一个重复区域。
3. 批量跳过：利用一个while循环，让cur一直向后移动，直到跳过所有值相同的节点。最后让pre.next = cur.next，直接把这一整段重复的“一刀切掉”。

3. 代码实现 (Python)

classSolution:defdeleteDuplicates(self,head:Optional[ListNode])->Optional[ListNode]:# 1. 只要头节点可能被删，就请出 dummydummy=ListNode(0,head)pre=dummywhilepre.nextandpre.next.next:# 检查接下来两个节点的值是否相同ifpre.next.val==pre.next.next.val:# 记录这个重复的值x=pre.next.val# 只要接下来的节点值等于 x，就不断跳过curr=pre.nextwhilecurrandcurr.val==x:curr=curr.next# 将 pre 的 next 指向第一个不等于 x 的节点pre.next=currelse:# 如果不重复，pre 才可以放心前进一步pre=pre.nextreturndummy.next

4. 关键逻辑点拨

• 为什么pre不直接移动？
  在发现重复时，pre.next = curr之后，pre不能立即后移。因为新接上的这个curr节点，可能又是另一组重复数字的开始。必须在下一轮循环中再次检查。
• 对比 83 题：
  • 83 题：保留重复项中的一个。所以发现重复时，cur.next = cur.next.next，cur本身不动。
  • 82 题：一个不留。所以需要一个内层循环把所有val相同的都走完，然后让pre跨越式连接。

5. 复杂度分析

• 时间复杂度：O(N)O(N)O(N)。虽然有嵌套循环，但每个节点最多只被访问两次（一次由curr扫描，一次作为pre.next），依然是线性时间。
• 空间复杂度：O(1)O(1)O(1)。

通过这两道题（83 和 82）的对比，感觉到dummy节点在处理“头节点可能消失”的问题时是多么好用了

whilecurrandcurr.val==x:

这行代码体现了 Python 中的两个重要概念：短路逻辑（Short-circuiting）和循环过滤。

1. 拆解这行代码

这行代码的作用是：“只要当前节点存在，并且它的值还是我们要找的重复值，就一直往后走。”

• while: 开启一个循环。
• curr: 检查curr是否为None。如果curr已经走到了链表的末尾（即空指针），这个条件就是False。
• and: 逻辑与操作。
• curr.val == x: 检查当前节点的值是否等于我们要删除的那个重复值x。

2. 为什么要加curr and ...？（防止报错）

这是这段代码最关键的地方。在链表操作中，我们经常会遇到空指针异常。

如果链表的结尾正好是一串重复数字，比如1 -> 2 -> 2 -> None：

1. 第一个2：curr存在，val是 2，进入循环。
2. 第二个2：curr存在，val是 2，进入循环。
3. 关键点：此时curr移动到了None。
4. 如果没有curr and，代码会直接执行None.val == 2。这时候程序会崩溃，抛出AttributeError: 'NoneType' object has no attribute 'val'。

Python 的短路原则：
在A and B中，如果A已经是False了，Python 根本不会去看B是什么。所以先判断curr是否存在，可以安全地保护后面的.val操作不报错。

3. 这种语法的目的：批量跳过

在第 82 题中，我们要“一个不留”地删除重复项。

假设链表是：pre -> 2 -> 2 -> 2 -> 3，此时x = 2。

• curr最初指向第一个2。
• while curr and curr.val == x:会让curr像跳格子一样：
  • 跳过第一个2
  • 跳过第二个2
  • 跳过第三个2
• 最后curr停在了3的位置。

退出循环后，我们执行pre.next = curr。
效果就是：pre的下一跳直接变成了3，中间那串2被整体切除了。

总结

这是一种非常经典的**“过滤重复区间”**的写法：

1. 用x记住那个“坏掉”的值。
2. 用while配合指针移动，把所有等于x的连续节点全部走完。
3. 利用and的短路特性保证代码的健壮性（鲁棒性）。

这种“先检查指针是否为空，再访问指针成员”的习惯，在写任何链表或树（Tree）的代码时都是必须具备的。