链表：单链表、双链表与虚拟头节点

简介

链表是一种基础且重要的线性数据结构，它通过节点（Node）的指针链接来组织数据，与数组在内存中连续存储的特性形成鲜明对比。链表的每个节点包含两个部分：存储数据元素的“数据域”和指向下一个节点地址的“指针域”。这种非连续的存储方式赋予了链表动态分配内存、高效插入与删除操作的天然优势，但同时也牺牲了通过索引进行随机访问的能力。在算法问题中，链表是考察指针操作、边界条件处理以及空间复杂度分析的绝佳载体。

本章将深入探讨链表的两种主要形态：单链表（Singly Linked List）和双链表（Doubly Linked List）。我们将从它们的节点结构出发，详细解析遍历、插入、删除等核心操作。更重要的是，我们将引入一个在解决链表问题时极其强大的技巧——虚拟头节点（Dummy Node），它能将复杂的边界条件处理统一化，极大地简化代码逻辑。最后，我们将通过反转链表、检测环、合并两个有序链表这三个经典问题，将理论知识付诸实践，展示如何运用这些概念和技巧优雅地解决算法挑战。

核心概念

节点结构与内存非连续特性

链表的基石是节点。一个单链表节点通常包含一个值（val）和一个指向下一个节点的指针（next）。双链表节点则在此基础上增加了一个指向前一个节点的指针（prev）。这些节点在内存中的分配是动态且不要求连续的，它们通过指针相互“链接”成一个逻辑上的序列。这与数组在内存中占据一块连续空间有本质区别。数组的优势在于通过索引（即内存地址偏移）可以在常数时间 O(1) 内访问任意元素；而链表要访问第 i 个元素，必须从头部开始逐个遍历，时间复杂度为 O(n)。然而，在链表已知节点位置进行插入或删除操作时，仅需修改相关指针，时间复杂度为 O(1)，这比数组在中间位置进行同类操作（需要移动后续所有元素，O(n)）要高效得多。

单链表与双链表的操作

单链表的操作相对简单，但单向性也带来了限制。遍历只能从头到尾。在指定节点后插入新节点，需要将新节点的 next 指向原节点的下一个节点，再将原节点的 next 指向新节点。删除指定节点后的节点，只需将当前节点的 next 指向下下个节点。但删除当前节点本身在单链表中是困难的，因为你无法直接获取其前驱节点。

双链表通过增加一个 prev 指针解决了这个问题。这使得它可以双向遍历，并且在已知节点位置时，无论插入还是删除该节点，都能在 O(1) 时间内完成，因为可以轻松访问其前驱和后继。当然，这需要维护更多的指针，在插入和删除时需要同时更新 next 和 prev 指针，操作稍显复杂，也占用稍多的内存空间。

虚拟头节点（Dummy Node）技巧

虚拟头节点是链表算法中一个至关重要的编程技巧。它是在原始链表头部之前额外添加的一个节点，其 val 值通常无关紧要（如设为 0 或 None），但它的 next 指针指向真正的链表头节点。引入虚拟头节点的核心目的是统一操作逻辑，简化边界条件处理。

考虑一个常见场景：需要删除链表中所有值为 target 的节点。如果不使用虚拟头节点，删除头节点的情况需要单独处理，因为头节点没有前驱节点。代码中会充斥着 if (head.val == target) 这样的条件判断。而使用虚拟头节点后，原链表的每一个节点（包括原头节点）都变成了“拥有前驱节点的节点”，删除操作可以用完全相同的逻辑来处理，最后只需返回 dummy.next 作为新链表的头即可。这个技巧在链表反转、合并、分区等问题中广泛应用，能显著降低代码的复杂度和出错概率。

实战示例

以下是一个完整的 Python 示例，展示了单链表类的实现，并运用虚拟头节点技巧解决了“删除链表中所有指定值节点”的问题。

class ListNode:
"""单链表节点定义"""
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class SinglyLinkedList:
"""单链表类，包含基本操作"""
def __init__(self):
# 初始化一个虚拟头节点，简化后续操作
self.dummy_head = ListNode()
self.size = 0
def get(self, index: int) -> int:
"""获取链表中第 index 个节点的值。如果索引无效，则返回 -1。"""
if index < 0 or index >= self.size:
return -1
cur = self.dummy_head.next
for _ in range(index):
cur = cur.next
return cur.val
def add_at_head(self, val: int) -> None:
"""在链表的第一个元素之前添加一个值为 val 的节点。"""
self.add_at_index(0, val)
def add_at_tail(self, val: int) -> None:
"""将值为 val 的节点追加到链表的最后一个元素。"""
self.add_at_index(self.size, val)
def add_at_index(self, index: int, val: int) -> None:
"""在链表中的第 index 个节点之前添加值为 val 的节点。"""
if index > self.size:
return
prev = self.dummy_head
for _ in range(index):
prev = prev.next
new_node = ListNode(val, prev.next)
prev.next = new_node
self.size += 1
def delete_at_index(self, index: int) -> None:
"""如果索引 index 有效，则删除链表中的第 index 个节点。"""
if index < 0 or index >= self.size:
return
prev = self.dummy_head
for _ in range(index):
prev = prev.next
prev.next = prev.next.next
self.size -= 1
def remove_elements(self, val: int) -> None:
"""删除链表中所有满足 node.val == val 的节点。"""
prev = self.dummy_head
cur = self.dummy_head.next
while cur:
if cur.val == val:
# 删除 cur 节点
prev.next = cur.next
self.size -= 1
# cur 指针前进，prev 指针不动（因为下一个节点可能也要删除）
cur = cur.next
else:
# 两个指针同时前进
prev = cur
cur = cur.next
# 注意：这里不需要单独处理头节点，因为虚拟头节点统一了逻辑
def main():
"""演示链表操作和虚拟头节点的威力"""
# 1. 创建链表并添加元素: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
linked_list = SinglyLinkedList()
for num in [6, 5, 4, 3, 6, 2, 1]:
linked_list.add_at_head(num)  # 注意添加顺序，最终链表顺序与列表相反
print("原始链表值序列: ", end="")
for i in range(linked_list.size):
print(linked_list.get(i), end=" -> ")
print("None")
# 2. 删除所有值为 6 的节点
linked_list.remove_elements(6)
print("删除所有6后: ", end="")
for i in range(linked_list.size):
print(linked_list.get(i), end=" -> ")
print("None")
# 3. 在索引2处插入值100
linked_list.add_at_index(2, 100)
print("在索引2插入100后: ", end="")
for i in range(linked_list.size):
print(linked_list.get(i), end=" -> ")
print("None")
if __name__ == "__main__":
main()

对比分析

最佳实践

1. 先画图，再写码：在处理复杂的指针操作（如反转、分组反转）时，务必在纸上画出链表节点的初始状态、中间步骤和最终状态。明确标出 cur, prev, next 等临时指针的位置，这是理清逻辑、避免指针丢失的关键。
2. 善用虚拟头节点：养成习惯，在解题开始时先问自己：“这个问题使用虚拟头节点会不会更简单？” 对于涉及链表头部可能被修改或删除的问题，这几乎总是最佳选择。
3. 警惕空指针和环：任何通过 .next 或 .val 访问节点属性前，都要确保当前节点引用不为 None。在遍历链表时，循环条件使用 while cur: 比 while cur.next: 更安全，后者在空链表时会出错。对于可能存在环的链表，使用快慢指针（Floyd判圈算法）进行检测。
4. 双指针技巧的运用：除了检测环的快慢指针，双指针在链表中还有很多应用，例如：寻找链表中点（快指针走两步，慢指针走一步）、寻找倒数第k个节点（一个指针先走k步）、判断两个链表是否相交（指针走完自身链表后切换到另一链表头）。
5. 完成操作后检查边界：代码编写完成后，务必用以下测试用例验证：空链表、只有一个节点的链表、操作头节点、操作尾节点。确保你的逻辑在所有边界情况下都正确。

经典问题解析思路

1. 反转链表：经典的双指针（或三指针）迭代法。初始化 prev = None, cur = head。在循环中，先保存 cur.next 到临时变量 nxt，然后将 cur.next 指向 prev，最后 prev 和 cur 同时前进（prev = cur, cur = nxt）。循环结束后，prev 就是新的头节点。递归法同样优雅，其核心思想是：假设已经反转了后续链表，那么只需将当前节点的下一个节点的 next 指向自己，并断开自己原来的 next 指向。
2. 检测环：使用快慢指针（Floyd Cycle Detection Algorithm）。初始化 slow = head, fast = head。在循环中，slow 每次走一步 (slow = slow.next)，fast 每次走两步 (fast = fast.next.next，注意空指针判断)。如果链表中存在环，快慢指针最终一定会相遇；如果 fast 走到 None，则说明链表无环。
3. 合并两个有序链表：虚拟头节点法的典范。创建一个 dummy 节点，并用一个 cur 指针指向它。比较两个链表 l1 和 l2 当前节点的值，将较小的那个节点接在 cur 后面，然后对应的链表指针和 cur 指针前进。当一个链表遍历完后，将 cur.next 直接指向另一个链表的剩余部分。最终返回 dummy.next。

小结

链表作为一种动态数据结构，其非连续存储的特性在插入和删除操作上具有独特优势。单链表与双链表根据指针数量的不同，在灵活性和操作复杂度上各有取舍。掌握虚拟头节点这一技巧，是写出简洁、健壮链表算法的关键，它能将复杂的边界条件转化为统一的处理流程。通过反转、检测环、合并等经典问题的反复练习，可以深刻理解指针操作的奥妙，并熟练运用双指针等高级技巧。链表是算法学习的基石，扎实掌握其原理与操作，将为后续学习更复杂的数据结构和算法打下坚实基础。

下一节：哈希表与集合的魔力