节点定义：
java
class ListNode { int val; ListNode next; ListNode(int v){ val=v; }}
套路速查
| 套路 | 出现信号 |
|---|---|
| 虚拟头 dummy | 删除/插入头节点、合并 |
| 快慢指针 | 找中点、判环、环入口、倒数第 K |
| 原地反转 | reverse、回文 |
| 分段处理 | K 个一组、区间反转、奇偶 |
| 哈希标记 | 相交链表、复制随机链表 |
2.1 虚拟头 dummy
需要删除或插入头节点的场景，用一个哨兵节点统一逻辑，省掉对 head 的特判。
java
ListNode dummy = new ListNode(-1);dummy.next = head;ListNode cur = dummy; // 遍历/操作……// 最后返回 dummy.next 即为新头经典用法——删除倒数第 N 个节点：快指针先走 N+1 步（因为从 dummy 出发），然后快慢同步走，快指针到 null 时慢指针正好在待删节点的前驱。
java
ListNode dummy = new ListNode(-1, head);ListNode fast = dummy, slow = dummy;for (int i = 0; i <= n; i++) fast = fast.next; // 多走一步，停在待删前驱while (fast != null) { fast = fast.next; slow = slow.next;}slow.next = slow.next.next; // 跳过待删节点return dummy.next;递归解法：
java
private int removeNthFromEndHelper(ListNode head, int n) { if (head == null) { return 0; } int index = removeNthFromEndHelper(head.next, n) + 1; if (index == n + 1) { ListNode next = head.next; if (next != null) { head.next = next.next; } } return index;} public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; removeNthFromEndHelper(dummy, n); return dummy.next;}2.2 快慢指针
java
ListNode middle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; // 偶数返回靠右}2.3 原地反转
递归反转过程图解
递归先走到尾节点；每层回溯时把后继节点指回当前节点，再断开当前节点的旧 next。
java
public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode next = reverseList(head.next); // 进行翻转 head.next.next = head; head.next = null; // 返回翻转后头部节点 return next; }2.4 分段处理
把链表按某种条件拆成若干段，逐段处理后重新串起来。核心框架：dummy 开头，每轮找出一段的头尾，断开、处理、接回。
java
ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy; while (prev.next != null) { // 找当前段 ListNode segHead = prev.next; ListNode segTail = prev; int count = 0; while (count < k && segTail.next != null) { segTail = segTail.next; count++; } // 不足 k 个 if (count < k) { break; } // 保存下一段 ListNode nextSeg = segTail.next; // 断开 segTail.next = null; // 处理当前段 ListNode newHead = reverse(segHead); ListNode newTail = segHead; // 接回 prev.next = newHead; newTail.next = nextSeg; // 移动到下一段 prev = newTail; } return dummy.next;}2.5 环入口（Floyd 判圈）
java
ListNode entry(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 第一次相遇 fast = head; while (slow != fast) { // 同速再走，第二次相遇即入口 slow = slow.next; fast = fast.next; } return slow; } } return null;}2.5.1 原理阐述
设链表头到环入口的距离为 a，环入口到第一次相遇点的距离为 b，环长为 L。
第一次相遇时，慢指针走了 a+b 步，快指针走了 a+b+nL 步（多绕了 n 圈）。快指针速度是慢指针的两倍：
plain text
2(a + b) = a + b + nL a + b = nL a = nL - bnL - b 的意思是：从相遇点出发，沿着环走 n 圈再往回退 b 步——正好到达环入口。等价于从相遇点出发继续往前走 (n-1)L + (L-b) 步也能到入口。而 a 是从头节点到入口的距离。两者相等。
所以当快指针跳回头节点，两指针同速（每次一步）前进时，头指针走 a 步到入口，相遇点指针走 nL - b 步也到入口——第二次相遇的位置正好是环入口。
本文由 AgentPlanFlow 生成