第15篇-链表基础-反转链表-合并链表与快慢指针

概述：为什么链表题容易让初学者卡住

学完栈和队列之后，我们继续看另一类非常基础、也非常高频的数据结构：链表。

数组和链表都可以存储一组元素。 但它们最大的区别在于：

数组依靠下标访问元素
链表依靠指针连接元素

这也导致链表题和数组题的思维方式很不一样。

数组题常常在想：

下标 i 怎么移动？
区间边界在哪里？

而链表题常常在想：

当前节点是谁？
下一个节点是谁？
指针应该先保存还是先修改？

很多初学者做链表题时，最容易出现的问题不是思路完全不会，而是：

• 指针断了
• 节点丢了
• 循环条件写错
• 返回了错误的头节点
• 忘记处理空链表或单节点链表

这篇文章会围绕链表最常见的四个方向展开：

学完这篇，你应该能看懂链表指针变化，并能独立写出反转链表、合并链表和快慢指针这几类高频题。

核心概念：链表到底是什么

链表是一种由节点组成的数据结构。

每个节点通常包含两部分：

• 值：当前节点存储的数据
• 指针：指向下一个节点的位置

单链表可以表示成：

head
|
v
[1] -> [2] -> [3] -> [4] -> null

在 Java 中，常见的链表节点定义如下：

public class ListNode {
int val;
ListNode next;

ListNode() {
}

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

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

其中：

• val 表示节点值
• next 表示下一个节点
• head 表示链表头节点

如果 head == null，说明链表为空。

链表和数组的区别

链表最核心的能力不是快速访问，而是：

通过修改指针关系，改变节点之间的连接方式。

链表题的本质不是操作值，而是操作节点之间的 next 指针。

基础操作：遍历链表

遍历链表是所有链表题的基础。

ListNode cur = head;

while (cur != null) {
System.out.println(cur.val);
cur = cur.next;
}

这里的 cur 是一个移动指针。 它从头节点开始，每次移动到下一个节点。

遍历过程：

cur
|
v
[1] -> [2] -> [3] -> null

cur
|
v
[1] -> [2] -> [3] -> null

cur
|
v
[1] -> [2] -> [3] -> null

当 cur == null 时，说明已经走到链表末尾。

遍历时常见错误

错误写法：

while (cur.next != null) {
cur = cur.next;
}

这个循环会停在最后一个节点，而不是遍历所有节点。 如果你需要处理每个节点，通常应该写：

while (cur != null) {
cur = cur.next;
}

当然，如果题目明确需要停在最后一个节点前面，才会使用 cur.next != null。

指针操作：为什么要先保存后修改

链表题最重要的一条经验是：

修改 next 指针前，先想清楚后面的节点会不会丢。

比如有链表：

1 -> 2 -> 3 -> null

如果当前 cur 指向节点 1：

cur.next = null;

那么节点 2 和节点 3 就无法再通过 cur 找到了。

所以在修改指针前，通常要先保存下一个节点：

ListNode next = cur.next;
cur.next = null;
cur = next;

这也是反转链表中最关键的动作。

经典题型一：反转链表

题目：

给定单链表头节点 head，请反转链表，并返回反转后的头节点。

示例：

输入：1 -> 2 -> 3 -> 4 -> 5 -> null
输出：5 -> 4 -> 3 -> 2 -> 1 -> null

解题思路

反转链表的核心是把每个节点的 next 指针反过来。

原链表：

1 -> 2 -> 3 -> null

反转后：

3 -> 2 -> 1 -> null

我们使用三个指针：

• prev：当前节点反转后应该指向的前一个节点
• cur：当前正在处理的节点
• next：提前保存 cur.next，防止链表断开后找不到后续节点

初始状态：

prev = null
cur = head

每一轮做三件事：

1. 保存 next = cur.next
2. 反转 cur.next = prev
3. 两个指针向后移动：prev = cur, cur = next

Java 代码实现

class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;

while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}

return prev;
}
}

执行过程

以 1 -> 2 -> 3 -> null 为例：

第一轮：

next = 2
1.next = null
prev = 1
cur = 2

结果：

1 -> null 2 -> 3 -> null

第二轮：

next = 3
2.next = 1
prev = 2
cur = 3

结果：

2 -> 1 -> null 3 -> null

第三轮：

next = null
3.next = 2
prev = 3
cur = null

结果：

3 -> 2 -> 1 -> null

最后 cur == null，循环结束，prev 就是新的头节点。

复杂度分析

• 时间复杂度：O(n)，每个节点处理一次
• 空间复杂度：O(1)，只使用常数个指针

反转链表的关键是先保存 next，再修改 cur.next，最后移动 prev 和 cur。

反转链表的递归写法

反转链表也可以用递归完成。

递归思路是：

先反转后面的链表，再把当前节点接到反转结果的末尾。

代码如下：

class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;

return newHead;
}
}

递归代码怎么理解

假设链表是：

1 -> 2 -> 3 -> null

递归调用：

reverseList(2)

会把后半部分反转成：

3 -> 2 -> null

此时 head 仍然是节点 1，并且原来的关系还是：

1 -> 2

要把 1 接到 2 后面，需要：

head.next.next = head;

也就是：

2 -> 1

然后断开原来的指向：

head.next = null;

否则会形成环：

1 <-> 2

递归写法更简洁，但对初学者来说不如迭代直观。 刷题时建议先熟练掌握迭代写法。

递归复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)，递归调用栈占用空间

经典题型二：合并两个有序链表

题目：

将两个升序链表合并为一个新的升序链表，并返回合并后的头节点。

示例：

输入：
1 -> 2 -> 4
1 -> 3 -> 4

输出：
1 -> 1 -> 2 -> 3 -> 4 -> 4

解题思路

这道题和归并排序中的合并过程很像。

每次比较两个链表当前节点的值：

• 谁小，就把谁接到结果链表后面
• 对应链表指针向后移动
• 重复直到其中一个链表为空
• 最后把剩余链表接到结果后面

这里常用一个技巧：虚拟头节点。

什么是虚拟头节点

虚拟头节点也叫 dummy 节点。

它不是最终答案中的真实节点，只是为了简化代码。

如果不用 dummy，就要单独处理第一个节点：

结果链表头节点到底应该是 l1 还是 l2？

用了 dummy 后，可以统一写成：

dummy -> 已合并部分

最后返回：

dummy.next

Java 代码实现

class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;

while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}

cur = cur.next;
}

if (list1 != null) {
cur.next = list1;
}
if (list2 != null) {
cur.next = list2;
}

return dummy.next;
}
}

为什么最后可以直接接上剩余链表

因为两个输入链表本身已经是升序的。

当其中一个链表为空时，另一个链表剩下的节点也已经有序。 所以不需要继续一个个比较，直接接到结果链表末尾即可。

复杂度分析

• 时间复杂度：O(n + m)，两个链表每个节点最多访问一次
• 空间复杂度：O(1)，只使用常数个额外指针

其中 n 和 m 分别是两个链表的长度。

虚拟头节点可以统一处理结果链表的连接逻辑，避免单独判断新链表头节点。

经典题型三：删除链表节点

删除节点也是链表题中的基础操作。

如果要删除某个值等于 val 的节点，常见写法如下：

class Solution {
public 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;
}
}

为什么删除节点也适合用 dummy

如果要删除的是头节点，比如：

6 -> 1 -> 2 -> null

并且要删除 6，那么头节点会发生变化。

如果不用 dummy，就需要单独处理头节点连续被删除的情况。 用了 dummy 后，所有节点都可以统一看作：

删除 cur.next

不管删除的是不是原来的头节点，逻辑都一致。

删除节点时的关键点

删除 cur.next 时，应该写：

cur.next = cur.next.next;

此时 cur 不应该立刻向后移动。 因为新的 cur.next 可能仍然是需要删除的节点。

只有当前节点后面的节点不需要删除时，才移动：

cur = cur.next;

经典题型四：快慢指针

快慢指针是链表题中的高频技巧。

它通常使用两个指针：

• slow：每次走一步
• fast：每次走两步

由于速度不同，它们可以用来解决很多问题：

• 找链表中点
• 判断链表是否有环
• 找环的入口
• 删除倒数第 N 个节点
• 判断回文链表

这一节先讲最基础的两个：找中点和判断环。

快慢指针例题一：寻找链表中点

题目：

给定单链表头节点 head，返回链表的中间节点。

如果有两个中间节点，通常返回第二个中间节点。

示例：

1 -> 2 -> 3 -> 4 -> 5
返回 3

1 -> 2 -> 3 -> 4 -> 5 -> 6
返回 4

解题思路

使用两个指针：

slow 每次走一步
fast 每次走两步

当 fast 到达链表末尾时，slow 正好走到中间位置。

Java 代码实现

class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

return slow;
}
}

为什么偶数长度返回第二个中点

以：

1 -> 2 -> 3 -> 4 -> 5 -> 6

为例。

当 fast 每次走两步到达末尾后，slow 会停在节点 4。 所以这个写法返回的是第二个中间节点。

如果题目要求返回第一个中间节点，可以调整循环条件。 但大多数入门题默认返回第二个中点。

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

快慢指针例题二：判断链表是否有环

题目：

给定一个链表，判断链表中是否有环。

有环链表示意：

1 -> 2 -> 3 -> 4
^ |
|_________|

解题思路

仍然使用快慢指针：

• slow 每次走一步
• fast 每次走两步

如果链表没有环，fast 最终会走到 null。

如果链表有环，fast 会在环中不断追赶 slow。 因为 fast 比 slow 每轮多走一步，所以它们最终一定会相遇。

Java 代码实现

public class Solution {
public boolean hasCycle(ListNode head) {
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;
}
}

为什么要判断 fast != null && fast.next != null

因为 fast 每次要走两步：

fast = fast.next.next;

如果 fast 或 fast.next 是 null，就会出现空指针异常。

所以循环条件必须保证：

fast 当前存在
fast 的下一个节点也存在

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

当链表题需要判断中点、长度差或是否成环时，可以让两个指针以不同速度移动。

进阶例题：删除链表倒数第 N 个节点

题目：

给定链表头节点 head 和整数 n，删除链表倒数第 n 个节点，并返回头节点。

示例：

输入：1 -> 2 -> 3 -> 4 -> 5, n = 2
输出：1 -> 2 -> 3 -> 5

解题思路

这道题也可以用快慢指针。

核心是让 fast 先走 n 步，然后 slow 和 fast 一起走。 当 fast 走到链表末尾时，slow 就在待删除节点的前一个位置。

为了方便删除头节点，仍然使用 dummy 节点。

Java 代码实现

class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;

ListNode fast = dummy;
ListNode slow = dummy;

for (int i = 0; i < n; i++) {
fast = fast.next;
}

while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}

slow.next = slow.next.next;
return dummy.next;
}
}

为什么从 dummy 开始

如果要删除的是第一个节点，例如：

1 -> 2 -> 3
n = 3

删除后头节点应该变成 2。 使用 dummy 可以统一处理这种情况。

slow 最终停在待删除节点的前一个节点。 如果待删除的是原头节点，那么 slow 正好停在 dummy 上。

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

常见坑点：链表题最容易错在哪里

1. 修改指针前没有保存后续节点

反转链表时，如果直接写：

cur.next = prev;
cur = cur.next;

这里的 cur.next 已经被改成了 prev，原来的下一个节点丢失了。

正确写法应该先保存：

ListNode next = cur.next;
cur.next = prev;
cur = next;

2. 返回了错误的头节点

反转链表后，新的头节点不是原来的 head，而是 prev。

合并链表时，如果用了 dummy，返回的不是 dummy，而是：

return dummy.next;

删除节点时，如果头节点可能变化，也应该返回：

return dummy.next;

3. 没有处理空链表和单节点链表

很多链表题都需要考虑：

head == null
head.next == null

迭代反转链表可以自然处理这两种情况。 但递归写法必须显式判断：

if (head == null || head.next == null) {
return head;
}

4. 快慢指针循环条件写错

如果代码中有：

fast = fast.next.next;

循环条件通常应该是：

while (fast != null && fast.next != null)

不要只判断：

while (fast != null)

否则 fast.next 可能为空。

5. 删除节点后指针移动错误

删除链表中所有等于 val 的节点时：

if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}

删除后不要立刻移动 cur。 因为新的 cur.next 可能仍然需要删除。

模板总结：链表题常用写法

链表遍历模板

ListNode cur = head;

while (cur != null) {
// 处理 cur
cur = cur.next;
}

反转链表模板

ListNode prev = null;
ListNode cur = head;

while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}

return prev;

虚拟头节点模板

ListNode dummy = new ListNode(0);
dummy.next = head;

ListNode cur = dummy;

while (cur.next != null) {
// 根据题目处理 cur.next
}

return dummy.next;

快慢指针模板

ListNode slow = head;
ListNode fast = head;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}

总结

链表题的难点不在于代码很长，而在于指针关系容易写乱。 你可以重点记住下面几句话：

• 链表节点通过 next 指针连接
• 修改指针前，先保存后续节点
• 反转链表使用 prev、cur、next
• 合并链表和删除节点常用 dummy 节点简化边界
• 快慢指针适合找中点、判环、删除倒数节点
• 如果头节点可能变化，通常应该考虑虚拟头节点
• 循环条件要和指针移动方式匹配，避免空指针异常

链表题一开始写慢一点很正常。 建议每次写代码前，先在纸上画出节点和指针，再决定每一步修改哪个 next。