难度: Medium
给定一个已排序的链表的头 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- 题目数据保证链表已经按升序 排列
Submission
运行时间: 48 ms
内存: 14.8 MB
# 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]:
if head is None or head.next is None:
return head
dummy = ListNode(next=head)
cur = dummy
while cur.next and cur.next.next:
if cur.next.val == cur.next.next.val:
val = cur.next.val
p = cur.next
while p and p.val == val:
p = p.next
cur.next = p
else:
cur = cur.next
return dummy.next
Explain
这个题解使用了虚拟头节点（dummy node）的技巧。首先判断链表为空或只有一个节点的情况直接返回。然后创建一个虚拟头节点dummy，指向链表头节点。使用cur指针遍历链表，当cur的后两个节点值相等时，记录下重复的值val，然后用指针p从cur的下一个节点开始遍历，跳过所有值等于val的节点，将cur的next指针指向p。如果cur的后两个节点值不等，则cur后移一位。最后返回dummy.next即为删除重复节点后的链表头节点。
时间复杂度: O(n)
空间复杂度: O(1)
# 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]:
# 处理空链表和单节点链表的特殊情况
if head is None or head.next is None:
return head
# 创建虚拟头节点，指向链表头
dummy = ListNode(next=head)
cur = dummy
# cur的后两个节点存在时循环
while cur.next and cur.next.next:
# 如果cur后两个节点值相等
if cur.next.val == cur.next.next.val:
# 记录重复的值
val = cur.next.val
p = cur.next
# p不为空且p的值等于val，一直后移p
while p and p.val == val:
p = p.next
# 跳过了所有值等于val的节点，将cur的next指针指向p
cur.next = p
else:
# cur的后两个节点值不等，cur后移
cur = cur.next
# 返回虚拟头节点之后的链表
return dummy.next
Explore
使用虚拟头节点可以简化链表操作，特别是在链表头部存在可能的删除操作时。如果头节点本身就是需要被删除的重复节点，直接操作原链表头节点将需要特殊处理来更新头节点的引用。虚拟头节点保证了头节点前总有一个静态的节点，这样在任何删除操作后都不需要单独更新头节点的引用，从而使代码更简洁、逻辑更清晰。
在while循环中，判断条件包括了`p不为空`（`while p and p.val == val`），确保了在移动指针p时，只要p不为空，就可以安全地访问p.val。这个条件有效防止了指针超出链表末尾的情况。如果p为空，循环会停止，这样就处理了链表末尾的节点。
是的，这种处理方式仍然有效。一旦检测到`cur.next.val == cur.next.next.val`，意味着至少有两个连续的节点值相同，代码会进入一个内部循环，继续检查并跳过所有后续相同值的节点。这确保了即使是超过两个的连续相同值也会被正确处理和删除。
在Python中，由于存在垃圾回收机制，当某个对象没有引用指向它时，它将被自动回收。在此题解中，当将`cur.next`指向p，原来指向的节点（即重复的节点）将没有引用指向它们，如果没有其他地方引用这些节点，它们将由垃圾收集器回收。因此，通常不会导致内存泄漏。但在没有垃圾回收的环境中，如C或C++，这种做法可能需要手动管理内存以防内存泄漏。