当前位置：首页 > news >正文

链表题解——移除链表元素【LeetCode】

news 2025/7/1 18:34:43

全部题目来自力扣，这里只做学习的记录，内容中部分为AI生成，有不对的地方可以评论或者私信哦~~

203. 移除链表元素

一、算法逻辑（每一步通顺讲解思路）

1️⃣ 初始化虚拟头节点和指针

创建一个哨兵节点 dummy，它的 next 指向原链表的头节点。这样即使头节点本身被删除，也能通过 dummy.next 返回正确结果。
再用 cur 指针从 dummy 开始遍历，用于构建新的链表。

2️⃣ 遍历链表并判断是否需要删除

使用 cur.next 来判断下一个节点是否存在；
如果 cur.next.val == val，说明找到了需要删除的节点；
- 这时直接跳过该节点：cur.next = cur.next.next；
- 删除操作不会向前推进 cur，因为跳过后还要检查新接上的节点；
否则，如果当前节点不是目标值，就将 cur 向后推进一位。

3️⃣ 返回新链表的头节点

删除操作完成后，返回的是 dummy.next，它指向的是链表的有效起始节点（不管原始头节点是否被删除）。

二、核心点总结

这段算法的核心思想是：

引入虚拟头节点，统一处理所有删除逻辑，避免特判头节点。

✅ 哨兵节点消除了对头节点是否是目标值的特殊处理；
✅ 通过操作 cur.next 删除下一个节点，避免在删除操作中提前丢失遍历控制；
✅ 整体逻辑清晰，边界处理优雅，具备高度可拓展性（可用于更复杂的删除规则中）

# 虚拟头节点法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextclass Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:# 创建虚拟头部节点以简化删除过程dummy_head = ListNode(next = head)# 遍历列表并删除值为val的节点current = dummy_headwhile current.next:if current.next.val == val:current.next = current.next.nextelse:current = current.nextreturn dummy_head.next