链表中篇：三道题三个坑，每个都不是你以为的那种错

文章目录

• 链表中篇：三道题三个坑，每个都不是你以为的那种错
• • 一、LeetCode 24：两两交换链表中的节点
  • • 题意
    • 最简写法：递归
    • 迭代写法（仅供对比）
  • 二、LeetCode 25：K 个一组翻转链表
  • • 题意
    • 正确写法
    • 坑：循环边界
    • 为什么"先递归后反转"比"先反转后递归"快？
  • 三、LeetCode 138：复制带随机指针的链表
  • • 题意
    • HashMap 方案
    • 两个坑，缺一个都会 WA
  • 总结

链表中篇：三道题三个坑，每个都不是你以为的那种错

你刷链表题，写完递归，思路清晰，提交——报错。 不是算法错了，是某个细节坑了你。

24、25、138，这三道题都有一个藏得很深的问题。这篇文章帮你把坑走完。

一、LeetCode 24：两两交换链表中的节点

题意

1→2→3→4 变成 2→1→4→3，每两个相邻节点交换。

最简写法：递归

public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode second = head.next;
head.next = swapPairs(second.next);
second.next = head;
return second;
}

三行完成一组交换，递归处理剩余部分。这已经是最简的写法，没有更短的方案。

递归终止：不足两个节点就直接返回，不用交换。

迭代写法（仅供对比）

public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode a = prev.next, b = prev.next.next;
prev.next = b;
a.next = b.next;
b.next = a;
prev = a;
}
return dummy.next;
}

迭代代码量是递归两倍，没有优势。直接用递归版本。

二、LeetCode 25：K 个一组翻转链表

题意

每 K 个节点为一组翻转，不足 K 个的尾部保持原顺序。

正确写法

public ListNode reverseKGroup(ListNode head, int k) {
ListNode check = head;
for (int i = 0; i < k; i++) {
if (check == null) return head; // 不足k个，直接返回
check = check.next;
}

ListNode prev = reverseKGroup(check, k); // 先递归后面
for (int i = 0; i < k; i++) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}

坑：循环边界

很多人写成 i <= k，导致多走一步，逻辑差一位。

为什么"先递归后反转"比"先反转后递归"快？

本质上时间复杂度一样，都是 O(n)。先递归后反转这种写法常数更小、逻辑更线性，JVM 内联效果更好。LeetCode 上的时间差异属于正常波动，不用纠结。

三、LeetCode 138：复制带随机指针的链表

题意

链表每个节点除了 next 还有一个 random 指针，可以指向任意节点或 null。深拷贝整条链表。

HashMap 方案

用 Map<原节点, 拷贝节点> 记录映射，遍历时按需创建拷贝节点。

public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node dummy = new Node(0);
Node cur = dummy;

for (Node p = head; p != null; p = p.next) {
map.putIfAbsent(p, new Node(p.val)); // 先存自己
Node clone = map.get(p);

if (p.random != null) {
map.putIfAbsent(p.random, new Node(p.random.val));
clone.random = map.get(p.random);
}

cur.next = clone;
cur = cur.next;
}

return dummy.next;
}

两个坑，缺一个都会 WA

坑1：先 put 自己，再处理 random

当 p.random == p（random 指向自身）时，如果先 put(p.random, …) 再 put(p, clone)，后者会覆盖前者，导致 random 和 next 链上的节点不是同一个对象。

顺序必须是：先 putIfAbsent(p, …) 存自己，再处理 random。

坑2：不要用 computeIfAbsent 嵌套调用

// 错误写法
Node clone = map.computeIfAbsent(p, k -> new Node(k.val));
clone.random = map.computeIfAbsent(p.random, k -> new Node(k.val)); // 当p.random==p时出bug

p.random == p 时，外层 computeIfAbsent 还没结束，内层又对同一个 key 调用，HashMap 内部实现会导致结果丢失。测试用例 [[1,0]] 就能复现。

总结

• LeetCode 24：递归三行是最优解，迭代反而更繁琐
• LeetCode 25：循环用 i < k，先确认够 k 个再翻转
• LeetCode 138：putIfAbsent 代替 computeIfAbsent，且先存自己再处理 random

链表题的难点不在算法本身，在于指针操作的顺序和边界。每一处细节都值得盯一眼。

觉得有帮助的话，点赞收藏支持一下，下篇会出这三道题的踩坑反思，把我们对话里的所有理解偏差整理成教学。