链表
链表通过节点链接组织元素。本文负责局部修改、反转、判环和节点身份。
1. 面试核心
先记住这几条，再读正文- 查找成本。 单链表随机访问和按值查找最坏为 O(n)，因为需要沿链接逐个节点前进。
- 插入与删除。 已知前驱时，单链表插入和删除只需修改少量链接，时间为 O(1)；寻找前驱的成本需要另算。
- 链表反转。 单链表反转需先保存后继，再修改当前链接。卡 · 反转单链表
- 环检测。 快慢指针判环耗时 O(n)，额外空间为 O(1)。卡 · 快慢指针与环入口
2. 节点与链接
单链表节点保存值和 next。双向链表还保存 prev，支持反向遍历。
head → A → B → C → null
在 A 后插入 X，先令 X.next=A.next，再令 A.next=X。若次序颠倒，原后缀会丢失。删除 B 时令 A.next=B.next，得到 A→C。
3. 反转单链表
static final class Node {
int value;
Node next;
Node(int value) { this.value = value; }
}
static Node reverse(Node head) {
Node previous = null;
Node current = head;
while (current != null) {
Node next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
previous 指向已反转前缀，current 指向待处理后缀。保存后继后，修改当前链接就不会丢失余下节点。输入 1→2→3，返回 3→2→1。时间 O(n)，额外空间 O(1)。实现要求无环，并会修改输入。
4. 快慢指针与环入口
两个指针从头出发，慢指针走一步，快指针走两步。快指针或其后继为空时，链表无环。有环时，两指针进入环后的距离每轮缩小一格。经过至多一个环长就会相遇。
设入口前长度为 a，环长为 L，相遇点距入口为 b。慢指针共走 a+b+qL 步。快指针走了两倍，两者路程差是环长的整数倍。因此 a+b 是 L 的倍数。
相遇后，将一个指针放回头部。两者改为每次走一步，再次相遇处就是入口。头部指针到入口需 a 步，环内指针也恰好回到入口。
5. 使用边界
空表、头节点删除与尾引用更新需明确处理。虚拟头节点可统一头部修改路径。单链表删除已知节点仍需前驱。复制后继值的技巧仅适用于非尾节点，且会改变节点身份。
判断两个无环链表相交，应比较节点引用。两指针分别走完 A+B 与 B+A，就能对齐共同后缀。相遇点是首个共享节点，无交点时共同到达空引用。值相同的两个节点仍可拥有不同身份。
6 · 面试题卡片
本页题目与参考回答
6.1 如何反转单链表，链接修改顺序是什么？
考察重点：后继保存、循环不变量与边界。
相关内容：反转单链表。
参考回答
逐个让当前节点指向已反转前缀即可。
改链前先保存后继，再推进到后继。循环结束时，前缀头就是新头。空表返回空，单节点保持尾部为空。
6.2 快慢指针相遇后，如何找到环入口？
考察重点：路程差与环长的关系。
相关内容：快慢指针与环入口。
参考回答
快慢指针相遇后，把一个指针移回头部，再让两者每次各走一步，下一次相遇就是环入口。
设头部到入口的距离为 a，入口沿前进方向到初次相遇点的距离为 b。初次相遇时，a+b 是环长的倍数，因此两者再走 a 步会在入口对齐。总时间为 O(n)，额外空间为 O(1)。
6.3 两个无环链表如何判断首个相交节点？
考察重点：节点身份与路径长度对齐。
相关内容：使用边界。
参考回答
按节点引用比较，两指针分别走 A+B 和 B+A。
两条路径总长相同，因此会对齐共享后缀。相遇处是首个共享节点，无交点时共同到达空引用。比较值会把独立的同值节点误当成交点。