链表题的关键是节点身份与引用更新顺序；画清每个指针在循环前后的含义比记忆代码更可靠。

🧭 什么时候考虑这个专题

头节点可能变化时使用虚拟头节点；需要中点或环时考虑快慢指针；局部改向前先保存后继。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点核心规则常见复杂度
按位置访问链表访问第 k 个节点需要从已知节点逐步移动按位置访问 O(n)
虚拟头节点哨兵节点可统一处理头节点删除与普通节点删除不改变主复杂度
节点身份链表相交与环检测通常比较节点引用而不是节点值比较引用 O(1)
快慢指针安全条件快指针走两步前必须保证 fast 与 fast.Next 可访问遍历 O(n)
反转引用顺序改写 current.Next 前必须先保存原来的 next时间 O(n)，空间 O(1)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

  • 按位置访问： 已经持有目标前驱引用时局部插入可以是 O(1)
  • 虚拟头节点： 返回结果时必须跳过哨兵本身
  • 节点身份： 值相同的两个节点仍可能属于不同链表
  • 快慢指针安全条件： 奇偶长度会让快指针分别停在末节点或 null
  • 反转引用顺序： 丢失 next 引用会让未处理后缀无法访问

C# 实现检查

  1. 方法签名与题目契约一致，不依赖控制台输入输出。
  2. 数值计算检查 int 溢出，必要时先提升为 long。
  3. 集合选择说明平均复杂度、顺序语义和重复值处理。
  4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
  5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

  • 按位置访问： 不要把“链表支持与数组相同的 O(1) 下标访问”当成规则。
  • 虚拟头节点： 不要把“虚拟头节点会成为业务链表的一部分”当成规则。
  • 节点身份： 不要把“节点值相等即可证明两个链表相交”当成规则。
  • 快慢指针安全条件： 不要把“只检查 fast 非 null 就可以访问 fast.Next.Next”当成规则。
  • 反转引用顺序： 不要把“只交换头尾引用就能反转整条链表”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。