LeetCode 82. 删除排序链表中的重复元素 II - Python3 实现

思路

因为可能会删除头节点，所以使用哑节点（dummy） 简化边界处理。

· prev 指向最后一个确定保留下来的节点
· curr 用于遍历链表

遍历时：

1. 如果 curr 和 curr.next 值相同，说明出现重复：
   · 记录重复值 dup = curr.val
   · 跳过所有值为 dup 的节点
   · 让 prev.next 指向跳过后的 curr
2. 如果值不同，说明 curr 是唯一的：
   · prev = curr
   · curr = curr.next

Python3 代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        curr = head

        while curr:
            # 出现重复
            if curr.next and curr.val == curr.next.val:
                dup = curr.val
                # 跳过所有值为 dup 的节点
                while curr and curr.val == dup:
                    curr = curr.next
                prev.next = curr
            else:
                prev = curr
                curr = curr.next

        return dummy.next

复杂度分析

指标 复杂度
时间 O(n)
空间 O(1)

测试用例

# 输入: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
# 输出: 1 -> 2 -> 5

# 输入: 1 -> 1 -> 1 -> 2 -> 3
# 输出: 2 -> 3

关键点

1. 哑节点：避免头节点被删除时单独处理。
2. 内层 while：一次性跳过所有重复节点。
3. 只保留唯一节点：只要当前节点与下一个节点值相同，就整个重复段都删除。