链表 (Linked Lists)

为什么链表很重要

链表支持在任意位置进行高效的插入和删除操作——而这些操作在数组中通常需要 $O(n)$ 的元素移动：

• 动态内存分配：节点散布在内存各处，不需要连续的内存空间。
• 高效增删：在已知位置插入或删除仅需 $O(1)$（只需更新指针）。
• 底层基石：是实现栈、队列、哈希表拉链法以及图邻接表的基础。
• 面试高频：快慢指针、翻转链表和环检测出现在 30% 以上的链表相关题目中。

实际影响：Java 的 LinkedHashMap 内部维护了一个双向链表来记录遍历顺序，这使得 entrySet() 的遍历复杂度是稳定的 $O(n)$。

---

核心概念

单向链表结构

每个节点包含数据和指向下一个节点的指针：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

双向链表

每个节点同时拥有 next 和 prev 指针：

• 优点：支持双向遍历；在已知节点引用时可实现 $O(1)$ 删除（无需寻找前驱节点）。
• 应用：浏览器前进/后退功能、编辑器的撤销/重做。

循环链表

尾节点重新指向头节点，形成一个闭环。

• 应用：操作系统的进程时间片轮转调度、循环播放列表。

---

核心技巧与模式

1. 哨兵节点 (Sentinel/Dummy Node)

创建一个虚构的头节点（通常值为 0），其 next 指向真正的头。

• 收益：消除处理“空链表”或“在头部插入”时的特殊逻辑判断。

2. 快慢指针 (Fast & Slow Pointers)

两个指针以不同速度（通常是 1 倍速和 2 倍速）移动。

• 应用场景：
  • 寻找中点：快指针到头时，慢指针恰好在中点。
  • 判断有环：若有环，快指针最终必会“套圈”追上慢指针。
  • 寻找倒数第 K 个节点：先让快指针走 K 步，然后同步移动。

3. 链表翻转 (List Reversal)

核心逻辑：在遍历过程中，不断将当前节点的 next 指向前驱节点。

• 迭代法：使用 prev, curr, nextTemp 三个指针协同。
• 递归法：代码更优雅，但需注意 $O(n)$ 的栈空间消耗。

---

面试高频题

Q1: 翻转链表 (简单)

思路：典型的三指针迭代。

Q2: 合并两个有序链表 (简单)

思路：使用哨兵节点。比较两个链表的头，谁小取谁，然后指针后移。

Q3: 环形链表 (简单)

思路：快慢指针。若快指针能遇到慢指针，则说明有环。

Q4: 删除链表的倒数第 N 个节点 (中等)

思路：快指针先走 $N+1$ 步，然后快慢指针同步走，直到快指针到头。此时慢指针正好在待删节点的前驱位置。

Q5: 相交链表 (简单)

思路：两个指针分别遍历 A+B 和 B+A。若相交，它们必会在交点相遇。

---

延伸阅读

• 双向队列 (Deque)：深入了解链表如何实现高效的头部和尾部操作。
• 跳表 (Skip List)：了解如何通过多级索引将链表查询优化到 $O(\log n)$。
• LeetCode：链表标签题目