加载中…
应用场景：频繁头部插删 · 实现栈/队列 · LRU
交互式动画演示，可调整参数并单步执行。
全屏打开链表（Linked List） 是一种线性数据结构，由若干节点组成，每个节点包含数据和指向下一个节点的指针。
graph LR N1([1 | ·]) -- next --> N2([2 | ·]) N2 -- next --> N3([3 | ·]) N3 -- next --> N4([4 | ·]) N4 -.-> NULL((null))
特点：
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n) | O(1) |
| 尾部插入 | O(1) 均摊 | O(n) / O(1)（带尾指针） |
| 中间插入 | O(n) | O(n)（需先遍历） |
| 内存连续 | ✅ | ❌ |
| 缓存友好 | ✅ | ❌ |
| 额外空间 | 无 | 每节点额外指针 |
选择：随机访问多 → 数组；插入删除多 → 链表。
head → A → B → C → D → null
只能从头到尾遍历，每个节点含一个 next 指针。
null ← A ⇄ B ⇄ C ⇄ D → null
每个节点含 prev 和 next 两个指针，可双向遍历。Java 的 LinkedList 就是双链表。
尾节点的 next 指向 head，构成环。
用途：约瑟夫问题、循环调度。
class ListNode {
int val;
ListNode next;
ListNode(int v) { val = v; }
}简化边界处理，统一所有位置的插入/删除逻辑。
public class LinkedListR<E> {
private Node<E> dummyHead;
private int size;
public LinkedListR() {
dummyHead = new Node<>(null);
size = 0;
}
public int getSize() { return size; }
public boolean isEmpty() { return size == 0; }
public void add(int index, E e) {
if (index < 0 || index > size) throw new IllegalArgumentException();
Node<E> prev = dummyHead;
for (int i = 0; i < index; i++) prev = prev.next;
prev.next = new Node<>(e, prev.next);
size++;
}
public void addFirst(E e) { add(0, e); }
public void addLast(E e) { add(size, e); }
public E get(int index) {
if (index < 0 || index >= size) throw new IllegalArgumentException();
Node<E> cur = dummyHead.next;
for (int i = 0; i < index; i++) cur = cur.next;
return cur.val;
}
public E remove(int index) {
if (index < 0 || index >= size) throw new IllegalArgumentException();
Node<E> prev = dummyHead;
for (int i = 0; i < index; i++) prev = prev.next;
Node<E> ret = prev.next;
prev.next = ret.next;
ret.next = null;
size--;
return ret.val;
}
}private Node<E> add(Node<E> node, int index, E e) {
if (index == 0) return new Node<>(e, node);
node.next = add(node.next, index - 1, e);
return node;
}特点：
判环：
boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}找环入口：快慢指针相遇后，一个回 head，一个从相遇点同步走，再次相遇即环入口。
找链表中点：
ListNode middle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}让"头部插入/删除"和"中间插入/删除"逻辑统一。
ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}迭代版：
ListNode reverse(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}递归版：
ListNode reverse(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a != null ? a : b;
return dummy.next;
}虽然表面上链表头部插入是 O(1)，但实际常数很大：
new Node()，触发一次堆分配。next 可能跳到任意内存地址，CPU cache 失效。经验：数据量大时（> 1e5），动态数组反而比链表更快，因为 cache locality 优势压过 O(n) 的劣势。
| 场景 | 使用 |
|---|---|
| LRU 缓存 | 双向链表 + 哈希表 |
| Linux 内核任务队列 | 双向链表 |
| 操作系统进程调度 | 双向链表 |
| 数据库事务 undo log | 双向链表 |
| Git 提交历史 | 链表 |
| 编辑器撤销栈 | 链表 |
head == null 或 head.next == null 要单独处理。next 再改指针。fast.next == null 会越界。equals 比较，不要用 ==（除非 int）。| 场景 | 推荐 |
|---|---|
| 大量随机访问 | 数组 |
| 大量插入删除 | 链表 |
| 既要搜索又要插入 | 跳表 / BST |
| 频繁查最值 | 堆 |
| 范围查询 | 跳表 / B 树 |
| 操作 | 时间（已知位置） | 时间（未知位置） |
|---|---|---|
| 头部插入 | O(1) | O(1) |
| 尾部插入 | O(1)（带 tail） | O(n) |
| 中间插入 | O(1) | O(n) |
| 头部删除 | O(1) | O(1) |
| 中间删除 | O(1) | O(n) |
| 查找 | O(n) | O(n) |
| 难度 | 题目 | 关键 |
|---|---|---|
| 🟢 | 反转链表 | 双指针 |
| 🟢 | 合并两个有序链表 | dummy + 双指针 |
| 🟢 | 删除链表的节点 | dummy |
| 🟡 | 反转链表 II | dummy + 区段反转 |
| 🟡 | 环形链表 II | 快慢指针 |
| 🟡 | 相交链表 | 双指针追及 |
| 🟡 | 删除链表的倒数第 N 个节点 | 快慢指针 |
| 🟡 | 奇偶链表 | 双指针重组 |
| 🟠 | K 个一组翻转链表 | 模拟 |
| 🟠 | 排序链表 | 归并 / 快慢 |
| 🔴 | LRU 缓存 | 哈希 + 双链表 |
| 🔴 | 二叉树展开为链表 | 链表拼接 |
链表 = 指针的艺术。
面试链表题，dummy 节点 + 双指针能解决 80% 的问题。
写完先画图，再小数据跑通（n=1, 2, 3），最后扩规模。
ListNode reverse(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
}