以下是 每日精讲 的三道经典题目：
环形链表、两个数组的交集、随机链表的复制
每道题都会给出清晰的思路、代码（Java实现）、复杂度分析，以及常见变种/易错点。
1. 环形链表（LeetCode 141 & 142）
题目描述
- 141：判断链表是否有环
- 142：如果有环，返回环的入口节点；没有环返回 null
核心思路
快慢指针（Floyd 判圈算法 / 龟兔赛跑）
- slow 每次走 1 步，fast 每次走 2 步
- 如果有环，fast 一定会在某个时刻追上 slow（相遇）
- 如果没有环，fast 会走到 null
如何找到环的入口？（142）
相遇后：
- 让其中一个指针（通常 slow）回到 head
- 另一个指针（fast）留在相遇点
- 两个指针都每次走 1 步
- 它们再次相遇的位置就是环的入口
证明（非常重要，面试常问）：
设链表头到环入口距离为 a，环的长度为 b，相遇点距离环入口为 x
第一次相遇时：
- slow 走了 a + x
- fast 走了 a + x + n×b（多转了 n 圈）
因为 fast 是 slow 的两倍速度，所以：
a + x + n×b = 2 × (a + x)
→ a + x = n×b
→ a = n×b – x
说明：从 head 走到环入口的距离 a，等于从相遇点再走 (n×b – x) 步刚好能到达环入口。
代码实现
// 141 判断是否有环
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
// 142 找到环的入口
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
// 第一阶段：找到相遇点
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
// 没有环
if (fast == null || fast.next == null) {
return null;
}
// 第二阶段：slow 回到 head，fast 留在相遇点，一起走一步
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // 或者 fast 都可以
}时间复杂度：O(n)
空间复杂度：O(1)
常见变种：
- 环的长度？
- 链表是否有环且环长为偶数？
- 找到环中距离入口最远的点？
2. 两个数组的交集（LeetCode 349 & 350）
349：两个数组的交集（元素唯一）
350：两个数组的交集 II（考虑重复元素）
思路对比
| 题目 | 推荐解法 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|
| 349 | HashSet | O(n + m) | O(min(n,m)) | 简单直接 |
| 350 | HashMap 计数 | O(n + m) | O(min(n,m)) | 需要记录出现次数 |
| 350（有序） | 双指针（排序后） | O(n log n + m log m) | O(1) 或 O(n+m) | 如果数组已排序更优 |
代码实现
// 349. 两个数组的交集（元素唯一）
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
for (int num : nums1) {
set.add(num);
}
List<Integer> list = new ArrayList<>();
for (int num : nums2) {
if (set.contains(num)) {
list.add(num);
set.remove(num); // 去重
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
// 350. 两个数组的交集 II（考虑重复）
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums1) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
List<Integer> list = new ArrayList<>();
for (int num : nums2) {
if (map.getOrDefault(num, 0) > 0) {
list.add(num);
map.put(num, map.get(num) - 1);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}进阶技巧：
- 如果数组已经排序 → 双指针（推荐面试时提）
- 如果其中一个数组非常小 → 可以用 HashSet 存小的那个
3. 随机链表的复制（LeetCode 138）
题目：复制一个带有随机指针的链表，每个节点有 next 和 random 两个指针。
最优解法（空间 O(n) → O(1) 进阶）
方法一：哈希表（最直观，面试最常见）
class Node {
int val;
Node next;
Node random;
// ...
}
public Node copyRandomList(Node head) {
if (head == null) return null;
// 第一遍：原节点 → 新节点 的映射
Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
// 第二遍：设置 next 和 random
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}方法二：空间 O(1)（链表拼接 + 拆分）（面试加分项）
步骤：
- 在原链表每个节点后面插入一个新节点（复制值）
- 设置新节点的 random 指针
- 拆分出新链表
public Node copyRandomList(Node head) {
if (head == null) return null;
// 第一步：复制节点，插入到原节点后面
Node cur = head;
while (cur != null) {
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
cur = copy.next;
}
// 第二步：设置 random 指针
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
// 第三步：拆分链表
Node dummy = new Node(0);
Node newCur = dummy;
cur = head;
while (cur != null) {
newCur.next = cur.next;
newCur = newCur.next;
cur.next = cur.next.next;
cur = cur.next;
}
return dummy.next;
}时间复杂度：O(n)
空间复杂度：O(1)（不计返回结果）
总结对比表
| 题目 | 核心解法 | 时间 | 空间 | 关键技巧 |
|---|---|---|---|---|
| 环形链表 | 快慢指针 | O(n) | O(1) | 相遇 → 入口证明 |
| 两个数组的交集 | HashSet / HashMap | O(n) | O(n) | 考虑重复元素时用 map 计数 |
| 随机链表复制 | 哈希表 / 链表拼接 | O(n) | O(n) / O(1) | 空间最优解是拼接 + 拆分 |
这三道题都是高频面试题，且考察的技巧（快慢指针、哈希映射、链表操作）在很多其他题目中反复出现。
有哪一道题想再深入（比如证明、变形题、代码优化）？或者今天想再加一道类似的题目？随时告诉我～
