快慢指针：链表中点、回文与随机指针复制
用快慢指针解决链表中点、回文判断、分区和带随机指针链表复制等经典问题。
1. 引言
链表（Linked List）是数据结构中的基石之一。与数组不同，它在内存中非连续存储，通过指针将各个节点串联起来。这种特性带来了高效的插入和删除操作，但也使其失去了通过索引随机访问的能力。
在算法实践中，链表问题常常因为无法“回头看”或“跳跃访问”而变得棘手，尤其是在面试中，我们经常会遇到“额外空间复杂度O(1)”的严苛要求。
本文将深入分析几个经典的链表算法问题，这些问题均来自于您提供的Java代码实现。我们将从一个核心技巧——“快慢指针”——出发，逐步解析回文链表判断、链表分区以及复杂链表的复制，并重点探讨如何在O(N)和O(1)的额外空间复杂度之间进行权衡与实现。
2. 核心技巧：快慢指针
2.1 什么是快慢指针？
快慢指针模式，顾名思义，就是使用两个指针（例如 slow 和 fast）以不同的速度在链表上移动。最经典的应用场景是：
slow指针每次移动一步。fast指针每次移动两步。
当 fast 指针到达链表末尾（即 fast == null 或 fast.next == null）时，slow 指针恰好位于链表的中点（或上中点）。
2.2 快慢指针的典型应用
这个简单的模式是解决众多链表问题的钥匙：
- 寻找链表中点：这是最直接的应用。根据
fast指针的停止条件，slow指针可以精确地停在奇数长度链表的中点，或偶数长度链表的上/下中点。 - 判断链表是否有环：如果链表有环，
fast指针最终会从后面“追上”slow指针（fast == slow）。 - 寻找环的入口点：在判断有环的基础上，可通过额外逻辑找到环的起始节点。
- 寻找倒数第K个节点：让
fast指针先走 K 步，然后slow和fast再一起走，当fast到达末尾时，slow就指向倒数第K个节点。
在接下来的问题中，我们将看到快慢指针如何被灵活运用来定位链表的关键节点。
3. 快慢指针求中点
第一个实践是快慢指针的基础应用：精确定位链表的不同“中点”位置。这在后续更复杂的问题（如回文判断）中是至关重要的一步。
3.1 奇数长度返回中点，偶数长度返回上中点
此场景下，slow 指针从第二个节点开始，fast 指针从第三个节点开始，保证 slow 在偶数长度时停在前面那个中点。
public Node midOrUpMidNode(Node head){
if (head == null || head.next == null || head.next.next == null) {
return head;
}
Node slow = head.next;
Node fast = head.next.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
3.2 奇数长度返回中点，偶数长度返回下中点
此场景下，slow 和 fast 都从第二个节点开始。当 fast 无法再走两步时，slow 恰好停在下中点位置。
public Node midOrDownMidNode(Node head) {
if (head == null || head.next == null) {
return head;
}
Node slow = head.next;
Node fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
3.3 奇数长度返回中点前一个，偶数长度返回上中点前一个
此场景下，slow 从头节点开始，fast 从第三个节点开始。这确保了 slow 始终比“中点/上中点”落后一步。
public Node midOrUpMidPreNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node slow = head;
Node fast = head.next.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
3.4 奇数长度返回中点前一个，偶数长度返回下中点前一个
此场景下，slow 从头节点开始，fast 从第二个节点开始。这确保了 slow 始终比“中点/下中点”落后一步。
public Node midOrDownMidPreNode(Node head) {
if (head == null || head.next == null) {
return null;
}
Node slow = head;
Node fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
4. 回文链表判断
判断一个链表是否为回文结构（例如 1 -> 2 -> 3 -> 2 -> 1）是一个经典问题。
4.1 思路一：栈与快慢指针 (O(N) 空间)
根据代码注释，第一种方法的思路非常清晰：
- 使用快慢指针找到链表的中点（偶数长度时为下中点）。
- 从该中点开始，将链表的后半部分节点依次压入栈（Stack）中。
- 遍历链表的前半部分，同时从栈中依次弹出节点。
- 比较前半部分的节点值与出栈的节点值，一旦发现不一致，则返回
false。 - 如果比较完毕均一致，则返回
true。
这种方法利用了栈“后进先出”的特性，巧妙地实现了后半部分链表的“反向”遍历。其额外空间复杂度为 O(N/2)，即 O(N)。
public boolean isPalindrome1(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head.next;
Node n2 = head.next;
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
Stack<Node> s = new Stack<>();
while (n1 != null) {
s.push(n1);
n1 = n1.next;
}
while(!s.isEmpty()) {
if (s.pop().val != head.val) {
return false;
}
head = head.next;
}
return true;
}
4.2 思路二：原地反转 (O(1) 空间)
第二种方法是进阶解法，旨在实现 O(1) 的额外空间复杂度：
- 使用快慢指针找到链表的中点（此实现中为上中点）。
- 将中点之后的后半部分链表进行原地反转。
- 设置两个指针，一个指向
head（前半部分），一个指向反转后的后半部分链表头部。 - 同步移动两个指针，逐一比较节点值。
- （关键步骤） 无论比较结果如何（即是否提前
break），都必须将后半部分链表再次反转，将其恢复为原始结构。 - 返回比较结果。
这种方法虽然步骤繁琐且需要反转两次，但它不使用任何额外的辅助集合，空间复杂度达到了O(1)。
public boolean isPalindrome2(Node head) {
if (head == null || head.next == null) {
return true;
}
if (head.next.next == null) {
return head.val == head.next.val;
}
// 1.
Node n1 = head.next;
Node n2 = head.next.next;
while (n2.next != null && n2.next.next != null) {
n1 = n1.next;
n2 = n2.next.next;
}
// 2.
n2 = n1.next;
n1.next = null;
Node n3 = null;
while (n2 != null) {
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
// 3.
n2 = head;
boolean rst = true;
Node downHead = n1;
while (n1 != null && n2 != null) {
if (n1.val != n2.val) {
rst = false;
break;
}
n1 = n1.next;
n2 = n2.next;
}
// 4.
n2 = downHead;
while (n2 != null) {
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
return rst;
}
5. 链表分区
此问题要求将一个链表按给定的 pivot 值划分为三部分：< pivot、== pivot 和 > pivot，且保持各部分内部节点的相对顺序不变。
5.1 思路一：辅助数组 (荷兰国旗)
这是一种易于理解但空间复杂度较高的方法：
- 遍历链表，计算总长度
count。 - 创建一个
Node类型的数组，大小为count。 - 再次遍历链表，将所有节点存入数组中。
- 在数组上执行“荷兰国旗问题”的划分（
nodeArrPartition方法），将数组按< pivot、== pivot和> pivot排序。 - 遍历数组，将排好序的节点重新串联成一个链表。
此方法空间复杂度为 O(N)，用于存储节点数组。
public Node listPartition1(Node head, int pivot) {
if (head == null || head.next == null) {
return head;
}
Node curr = head;
int count = 0;
while (curr != null) {
count++;
curr = curr.next;
}
curr = head;
Node[] arr = new Node[count];
for (int i = 0; curr != null; i++, curr = curr.next) {
arr[i] = curr;
}
// 荷兰国旗排序
nodeArrPartition(arr, pivot);
head = arr[0];
for (int i = 1; i < arr.length; i++) {
arr[i - 1].next = arr[i];
}
arr[arr.length - 1].next = null;
return arr[0];
}
public void nodeArrPartition(Node[] arr, int pivot) {
int small = -1;
int big = arr.length;
int index = 0;
while (index < big) {
if (arr[index].val < pivot) {
swap(arr, index, small + 1);
small++;
index++;
} else if (arr[index].val == pivot) {
index++;
} else {
swap(arr, index, big - 1);
big--;
}
}
}
public void swap(Node[] arr, int a, int b) {
Node temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
5.2 思路二：原地分区 (O(1) 空间)
这是一种精巧的 O(1) 空间解法，它通过有限的几个指针来构建三个新的（逻辑上的）子链表：
- 创建6个指针，分别代表“小于区”的头(sH)尾(sT)、“等于区”的头(eH)尾(eT)、“大于区”的头(bH)尾(bT)。
- 遍历原始链表，逐个拆下节点（
head）。 - 根据
head.val与pivot的关系，将其挂载到对应区域的尾指针（sT, eT 或 bT）上。 - 如果该区域是第一次添加节点，则头尾指针都指向该节点。
- 遍历结束后，得到了三个独立的子链表。
- 最后，将这三个子链表（小于区、等于区、大于区）按顺序首尾相连。
-
连接示意：
sT.next = eH (如果 eH 为 null，则 sT.next = bH)
eT.next = bH
- 返回新链表的头节点（
sH、eH或bH，取决于哪个区域不为空）。
public Node listPartition2(Node head, int pivot) {
if (head == null || head.next == null){
return head;
}
Node sH = null;
Node sT = null;
Node eH = null;
Node eT = null;
Node bH = null;
Node bT = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = null;
if (head.val < pivot) {
if (sH == null) {
sH = head;
sT = head;
} else {
sT.next = head;
sT = sT.next;
}
} else if (head.val > pivot) {
if (bH == null) {
bH = head;
bT = head;
} else {
bT.next = head;
bT = bT.next;
}
} else {
if (eH == null) {
eH = head;
eT = head;
} else {
eT.next = head;
eT = eT.next;
}
}
head = next;
}
// 小于区连等于区
if (sT != null) {
sT.next = (eH != null ? eH : bH);
}
// 等于区连大于区
if (eT != null) {
eT.next = bH;
}
return sH != null ? sH : (eH != null ? eH : bH);
}
6. 复制带随机指针的链表
这是一个难度较高的问题。链表节点除了 next 指针外，还有一个 rand 指针，它可能指向链表中的任意一个节点或 null。目标是深拷贝这个链表。
6.1 思路一：哈希表 (O(N) 空间)
利用哈希表（HashMap）可以直观地解决这个问题：
- 创建一个
HashMap<Node, Node>，用于存储“老节点”到“新节点”的映射。 - 第一次遍历原链表：每遇到一个老节点，就创建一个对应的新节点（只复制
val），并将<老节点, 新节点>存入哈希表。 - 第二次遍历原链表：再次从
head开始，设当前老节点为curr。- 通过哈希表找到
curr对应的新节点newNode = hm.get(curr)。 - 设置
newNode.next = hm.get(curr.next)。 - 设置
newNode.rand = hm.get(curr.rand)。
- 通过哈希表找到
- 返回
hm.get(head)，即新链表的头节点。
此方法逻辑清晰，但需要 O(N) 的额外空间来存储哈希表。
public static Node copyListWithRand1(Node head) {
if (head == null) return null;
HashMap<Node, Node> hm = new HashMap<>();
Node curr = head;
while (curr != null) {
Node newNode = new Node(curr.val);
hm.put(curr, newNode);
curr = curr.next;
}
curr = head;
Node newHead = hm.get(curr);
while (curr != null) {
hm.get(curr).next = hm.get(curr.next);
hm.get(curr).rand = hm.get(curr.rand);
curr = curr.next;
}
return newHead;
}
6.2 思路二：原地实现 (O(1) 空间)
这是一种极为精妙的 O(1) 空间解法，它通过修改原链表的 next 指针，将新老节点“编织”在一起，共分三步：
-
第一步：复制并“编织”
遍历原链表，在每个老节点 curr 后面创建一个新节点 copyNode，并将 copyNode 插入到 curr 和 curr.next 之间。
- 原：
1 -> 2 -> 3 - 后：
1 -> 1' -> 2 -> 2' -> 3 -> 3'
- 原：
-
第二步：设置 rand 指针
再次遍历这个“编织”后的链表（注意此时 curr 每次跳两步）。对于每个老节点 curr，其 rand 指针指向的也是一个老节点 curr.rand。那么，curr 对应的复制节点 curr.next (即 curr') 的 rand 指针，就应该指向 curr.rand 对应的复制节点，即 curr.rand.next。
curr.next.rand = (curr.rand != null) ? curr.rand.next : null;
-
第三步：拆分链表
将“编织”链表拆分为两个独立的链表（原链表和新链表）。这需要细致地重设 next 指针，将原链表恢复原状，同时将新链表串联起来。
public static Node copyListWithRand2(Node head) {
if (head == null) return null;
// 1.
Node curr = head;
Node next = null;
while (curr != null) {
next = curr.next;
curr.next = new Node(curr.val);
curr.next.next = next;
curr = next;
}
// 2.
curr = head;
while (curr != null) {
curr.next.rand = (curr.rand != null ? curr.rand.next : null);
curr = curr.next.next;
}
// 3.
curr = head;
Node newHead = head.next;
while (true) {
next = curr.next.next;
if (next == null) {
curr.next = null;
break;
}
curr.next.next = next.next;
curr.next = next;
curr = next;
}
return newHead;
}