链表技巧总结：双指针的七大应用场景
侧重：双指针技巧在单链表算法中的7大应用场景，每种技巧对应1-2道经典LeetCode题目
一句话总结
本文系统总结了单链表算法中双指针技巧的7种核心应用，覆盖合并、分解、查找、环检测、交点判断等常见场景，每种技巧都配有Java实现和LeetCode对应题目。
核心要点
1. 合并两个有序链表
对应题目：LeetCode 21 / 力扣 21
核心思路：类似"拉拉链"，用两个指针分别遍历两个链表，每次取较小节点接入结果链表。
关键技巧：使用**虚拟头结点（dummy）**简化边界处理——当需要创造一条新链表时，虚拟头结点可以避免处理空指针的情况。
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
if (p1 != null) p.next = p1;
if (p2 != null) p.next = p2;
return dummy.next;
}
2. 链表的分解
对应题目：LeetCode 86 / 力扣 86（分隔链表）
核心思路：将原链表分解为两个子链表（小于x / 大于等于x），最后拼接。类似合并有序链表的逆操作。
关键技巧：
- 使用两个虚拟头结点
dummy1、dummy2分别管理两个子链表 - 必须断开原链表节点的next指针，否则结果链表可能包含环
ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(-1), dummy2 = new ListNode(-1);
ListNode p1 = dummy1, p2 = dummy2;
ListNode p = head;
while (p != null) {
if (p.val >= x) {
p2.next = p;
p2 = p2.next;
} else {
p1.next = p;
p1 = p1.next;
}
ListNode temp = p.next;
p.next = null; // 断开原链接
p = temp;
}
p1.next = dummy2.next;
return dummy1.next;
}
3. 合并 k 个有序链表
对应题目：LeetCode 23 / 力扣 23
核心思路：使用**优先级队列（最小堆）**快速获取k个节点中的最小值，逐步构建结果链表。
时间复杂度：O(N log k)，其中k是链表条数，N是所有链表的节点总数。
ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b) -> (a.val - b.val));
for (ListNode head : lists) {
if (head != null) pq.add(head);
}
while (!pq.isEmpty()) {
ListNode node = pq.poll();
p.next = node;
if (node.next != null) pq.add(node.next);
p = p.next;
}
return dummy.next;
}
4. 寻找单链表的倒数第 k 个节点
对应题目：LeetCode 19 / 力扣 19（删除链表的倒数第N个结点）
核心思路：快慢指针——快指针先走k步，然后快慢指针同步前进，快指针到达末尾时，慢指针恰好指向倒数第k个节点。
关键技巧：删除倒数第n个节点时，需要先找到倒数第n+1个节点，同样使用虚拟头结点处理边界。
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
ListNode p2 = head;
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
return p2;
}
// 删除倒数第 n 个节点
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode x = findFromEnd(dummy, n + 1); // 找倒数第 n+1 个
x.next = x.next.next; // 删除
return dummy.next;
}
5. 寻找单链表的中点
对应题目：LeetCode 876 / 力扣 876
核心思路：快慢指针——慢指针每次走1步，快指针每次走2步，快指针到达末尾时，慢指针指向中点。
注意：当链表长度为偶数时，返回的是靠后的那个中点。
ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
6. 判断单链表是否包含环并找出环起点
对应题目：LeetCode 141（环形链表）、LeetCode 142（环形链表 II）
判断环：快慢指针，相遇则有环，走到空则无环。
找环起点（LeetCode 142）：
- 快慢指针相遇后，将任一个指针重新指向head
- 两个指针以相同速度前进
- 再次相遇的节点就是环的起点
原理：设环起点到head距离为 k-m，相遇点到环起点距离为 m，快指针比慢指针多走 k 步（k 是环长度的整数倍）。从相遇点走 k-m 步或从头走 k-m 步都能到达环起点。
// 判断是否有环
boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
// 找到环的起点
ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
if (fast == null || fast.next == null) return null;
// 重新指向头结点，同步前进
fast = head;
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
7. 判断两个单链表是否相交并找出交点
对应题目：LeetCode 160 / 力扣 160
核心思路：让两个指针 p1、p2 分别遍历A、B链表，走到末尾后转到另一条链表头部继续。这样两个指针走的路程相同（A+B），会在交点处相遇；如果不相交，则同时走到null。
另一种思路：计算两链表长度差，让长链表的指针先走长度差步，然后同步前进比较。
第三种思路（评论区）：将一条链表首尾相连，转换为"寻找环起点"问题。
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
if (p1 == null) p1 = headB;
else p1 = p1.next;
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1; // 相交返回交点，不相交返回null
}
时间复杂度总结
| 技巧 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 合并两个有序链表 | O(N+M) | O(1) | N、M为两链表长度 |
| 链表分解 | O(N) | O(1) | 遍历一次 |
| 合并k个有序链表 | O(N log k) | O(k) | 优先级队列开销 |
| 倒数第k个节点 | O(N) | O(1) | 一次遍历（快慢指针） |
| 寻找中点 | O(N) | O(1) | 一次遍历（快慢指针） |
| 判断环/找环起点 | O(N) | O(1) | 快慢指针 |
| 判断交点 | O(N) | O(1) | 双指针拼接逻辑 |
通用技巧总结
虚拟头结点（Dummy Head）使用时机
何时使用：当你需要创造一条新链表的时候（合并、分解等），使用虚拟头结点可以简化边界情况的处理。
双指针模式
| 模式 | 快指针速度 | 慢指针速度 | 应用场景 |
|---|---|---|---|
| 倒数第k个 | k步领先 | 同步 | 从后向前定位 |
| 寻找中点 | 2步/次 | 1步/次 | 定位中间位置 |
| 环检测 | 2步/次 | 1步/次 | 判断是否有环 |
相关题目
| LeetCode | 力扣 | 难度 | 对应技巧 |
|---|---|---|---|
| 21. Merge Two Sorted Lists | 21. 合并两个有序链表 | 简单 | 合并两个有序链表 |
| 86. Partition List | 86. 分隔链表 | 中等 | 链表分解 |
| 23. Merge k Sorted Lists | 23. 合并 K 个升序链表 | 困难 | 合并k个有序链表 |
| 19. Remove Nth Node From End of List | 19. 删除链表的倒数第 N 个结点 | 中等 | 倒数第k个节点 |
| 876. Middle of the Linked List | 876. 链表的中间结点 | 简单 | 寻找中点 |
| 142. Linked List Cycle II | 142. 环形链表 II | 中等 | 环检测与环起点 |
| 160. Intersection of Two Linked Lists | 160. 相交链表 | 简单 | 判断交点 |
| 141. Linked List Cycle | 141. 环形链表 | 简单 | 判断环 |
| LCR 140. 训练计划 II | LCR 140. 训练计划 II | 简单 | 倒数第k个节点 |
相关概念
- 链表：链式存储的线性数据结构
- 单链表：每个节点只含后继指针的单向链表
- 虚拟头尾节点：通过虚拟节点统一链表操作逻辑的技巧
- 优先级队列：基于二叉堆实现，按优先级顺序取出元素
- 二叉堆：完全二叉树，sink/swim操作，优先级队列的底层结构
- 双指针：本文核心方法论
- 快慢指针：双指针的特例，用于中点查找和环检测
相关实体
- labuladong：算法学习平台 labuladong.online 作者
- leetcode：全球知名的在线算法题库与编程面试准备平台
总结
双指针技巧是单链表算法的核心工具：快慢指针用于定位（中点、倒数第k个、环检测），双指针拼接用于解决交点问题，虚拟头结点则是创造新链表时的通用简化技巧。掌握这7种模式，可以覆盖大部分单链表算法题。