数据结构与算法 / 系统课时
虚拟头节点的使用
虚拟头节点的使用
虚拟头节点在真实链表之前提供一个稳定前驱,使删除头节点、连续删除和构建结果链表都能使用统一逻辑。本课将通过删除与合并示例说明 dummy、tail 和 dummy.next 的职责。
学习目标
- 理解虚拟头节点只承担辅助作用
- 使用统一前驱处理头部与连续删除
- 正确返回真实链表入口
dummy.next
虚拟头节点的本质
创建 dummy = ListNode(0, head) 后,结构变为 dummy -> head -> ...。原首元节点现在也有前驱,因此删除任意真实节点都可以修改其前驱的 next。
dummy 的值只是占位,不参与业务计算,不计入链表长度,也不应出现在输出中。算法结束时必须返回 dummy.next,而不是 dummy。

删除与构建规则
删除指定值时,从 dummy 开始维护前驱 prev,检查 prev.next。删除成功后不要立即移动 prev,因为新的 prev.next 可能仍是需要删除的连续目标;只有当前后继保留时,才把 prev 向后推进。
构建或合并结果链表时,dummy 始终固定作为入口,tail 指向当前最后一个节点。每次追加后只移动 tail,最终通过 dummy.next 取得第一个真实节点。
主示例
下面的程序先删除所有值为 2 的节点,再合并两条有序链表。两个操作都使用虚拟头节点消除首次处理和头部边界分支。
python
from dataclasses import dataclass
from typing import Optional
@dataclass
class ListNode:
value: int
next: Optional["ListNode"] = None
def from_list(values: list[int]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
for value in values:
tail.next = ListNode(value)
tail = tail.next
return dummy.next
def to_list(head: Optional[ListNode]) -> list[int]:
result: list[int] = []
current = head
while current is not None:
result.append(current.value)
current = current.next
return result
def remove_value(
head: Optional[ListNode],
target: int,
) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
while prev.next is not None:
if prev.next.value == target:
# 删除后保持 prev 不动,继续检查新的后继
prev.next = prev.next.next
else:
prev = prev.next
return dummy.next
def merge_sorted(
first: Optional[ListNode],
second: Optional[ListNode],
) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
while first is not None and second is not None:
if first.value <= second.value:
tail.next = first
first = first.next
else:
tail.next = second
second = second.next
tail = tail.next
tail.next = first if first is not None else second
return dummy.next
def main() -> None:
removed = remove_value(from_list([2, 1, 2, 2, 3]), 2)
merged = merge_sorted(from_list([1, 4, 7]), from_list([2, 3, 8]))
print(to_list(removed))
print(to_list(merged))
if __name__ == "__main__":
main()预期输出:
text
[1, 3]
[1, 2, 3, 4, 7, 8]边界与常见错误
空链表也可以安全接到 dummy.next,因此无需单独创建首个真实节点。合并时某一条链表耗尽后,要把另一条链表的剩余部分接到 tail.next,否则尾部节点会丢失。
最常见的错误是返回 dummy、把占位值参与比较、删除后仍移动 prev 而跳过连续目标,以及构建过程中移动 dummy 导致入口丢失。固定 dummy、只移动 prev 或 tail,可以显著降低这些风险。
按自己的节奏,确认真正理解。