Take away
1. dummy节点
代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是
dummy 节点。如果不使用 dummy 虚拟节点，需要额外处理指针 p 为空的情况。而有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。
比如说，让你把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？再比你想把一条链表分解成两条链表，是不是也在创造新链表？这些情况都可以使用虚拟头结点简化边界情况的处理。
2. 双指针
使用双指针可以对链表合并、分裂、判断链表是否有环等。
一 链表双指针
双指针解题常用于链表问题。常见题目包括
LeetCode | 力扣 | 难度 |
🟢 | ||
🔴 | ||
🟠 | ||
🟢 | ||
🟠 | ||
🟢 | ||
🟠 | ||
🟢 |
1. 合并两个有序列表
链表问题要多用虚拟头结点，可以避免很多空指针问题。同时还可以较好的返回需要的节点。
eg:
ListNode dummy = new ListNode(-1); dummy.next = head; ... return dummy.next;
2. 合并N个有序列表
优先级队列（队列形式实现完全二叉树）
// 使用在合并n个有序链表时，快速选择下一个最小头结点列表 // 优先级队列，最小堆 PriorityQueue<ListNode> pQueue = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));
3. 删除倒数第n个节点
双指针的常用方法是快慢指针。通过快慢指针可解决环形链表等问题。以下是使用双指针寻找倒数节点示例
private ListNode findFromEnd(ListNode node, int n) { ListNode slow = node; ListNode fast = node; for (int i = 0; i < n; i++) { fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; }
4. 单链表的中点
经典的快慢指针使用示例。重点在于退出条件的判断，避免空指针。
public ListNode middleNode(ListNode head) { ListNode fast = head; ListNode slow = head; // 重点在于判断循环停止的边界。 while(fast!=null && fast.next!=null){ fast = fast.next.next; slow = slow.next; } return slow; }
5. 判断链表中是否有环&进阶
判断链表有环和找链表中点基本相同，只要判断是否快慢节点有重合。
进阶：
如果链表有环，如何找到环的入口。
根据：
f=2s （快指针每次2步，路程刚好2倍）
f = s + nb (相遇时，刚好多走了n圈）
推出：s = nb
从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步
public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; Boolean isCycle = false; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { isCycle = true; break; } } // 无环状态 if (!isCycle) { return null; } ListNode find = head; while (find != slow) { find = find.next; slow = slow.next; } return find; }
二 链表反转
这里主要有两种思路。一种是原地反转（迭代反转），比较好想到，想要注意实现细节；另一种是使用递归的思想，定义递归方法，然后实现反转。
2.1 反转整个链表
1. 问题描述
给定链表
1 → 2 → 3 → 4 → 5，反转后应得到 5 → 4 → 3 → 2 → 1。2. 核心思路
反转链表的核心是逐个修改节点的
next 指针方向 。需要三个指针协调工作：prev：记录当前节点的前一个节点
curr：当前处理的节点
next：保存当前节点的下一个节点（防止链表断裂）
3. 迭代思路
class Solution { // 反转以 head 为起点的单链表 public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; // 临时保存下一个节点 curr.next = prev; // 反转指针 prev = curr; // 指针后移 curr = nextTemp; } return prev; } }
4. 递归思路
递归反转单链表的关键在于，这个问题本身是存在子问题结构的。
通过递归函数的定义，把原问题分解成若干规模更小、结构相同的子问题，最后通过子问题的答案组装原问题的解。
public class ReverseLinkedList { // 递归法反转整个链表 public static ListNode reverseListRecursive(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseListRecursive(head.next); head.next.next = head; // 将后继节点指向当前节点 head.next = null; // 断开原连接防止循环 return newHead; } }
2.2 反转前 N 个链表节点
1 迭代方法（推荐）
ListNode reverseN(ListNode head, int n) { if (head == null || head.next == null) { return head; } ListNode pre, cur, nxt; pre = null; cur = head; nxt = head.next; while (n > 0) { cur.next = pre; pre = cur; cur = nxt; if (nxt != null) { nxt = nxt.next; } n--; } // 此时的 cur 是第 n + 1 个节点，head 是反转后的尾结点 head.next = cur; // 此时的 pre 是反转后的头结点 return pre; }
这里有两个关键点
- 每次循环开始的时候，pre 和 cur 中间是没有连接的，pre.next 是 pre 左边的，cur.next 是 cur 右边的。
- 循环结束后，要将左右两段再连起来。如下：head 是 1，cur 是 4，pre 是 3
2. 递归方法
// 后驱节点 ListNode successor = null; // 反转以 head 为起点的 n 个节点，返回新的头结点 ListNode reverseN(ListNode head, int n) { if (n == 1) { // 记录第 n + 1 个节点 successor = head.next; return head; } // 以 head.next 为起点，需要反转前 n - 1 个节点 ListNode last = reverseN(head.next, n - 1); head.next.next = head; // 让反转之后的 head 节点和后面的节点连起来 head.next = successor; return last; }
2.3 反转链表中的一部分（LeetCode 92）
1. 问题升级
给定链表
1 → 2 → 3 → 4 → 5，反转第 2 到第 4 个节点，得到 1 → 4 → 3 → 2 → 5。2. 关键挑战
- 定位反转区间的前驱节点 和后继节点
- 处理反转后的连接问题
- 考虑头节点可能被修改的边界情况
3. 实现步骤
- 定位起始位置 ：遍历到第
m-1个节点（记为pre）
- 反转区间内节点 ：对
m到n的节点进行反转
- 重新连接链表 ：将
pre.next连接到反转后的头部，原头部连接到后继节点
class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (m == 1) { return reverseN(head, n); } // 找到第 m 个节点的前驱 ListNode pre = head; for (int i = 1; i < m - 1; i++) { pre = pre.next; } // 从第 m 个节点开始反转 pre.next = reverseN(pre.next, n - m + 1); return head; } ListNode reverseN(ListNode head, int n) { if (head == null || head.next == null) { return head; } ListNode pre, cur, nxt; pre = null; cur = head; nxt = head.next; while (n > 0) { cur.next = pre; pre = cur; cur = nxt; if (nxt != null) { nxt = nxt.next; } n--; } // 此时的 cur 是第 n + 1 个节点，head 是反转后的尾结点 head.next = cur; // 此时的 pre 是反转后的头结点 return pre; } }
2.4 K 个一组反转链表
1. 问题描述
给定链表
1 → 2 → 3 → 4 → 5，当 k=2 时反转为 2 → 1 → 4 → 3 → 5。若最后一组不足 k 个节点则保持原顺序。2. 问题分析
认真思考一下可以发现这个问题具有递归性质。
比如说我们对这个链表调用
reverseKGroup(head, 2)，即以 2 个节点为一组反转链表：如果我设法把前 2 个节点反转，那么后面的那些节点怎么处理？后面的这些节点也是一条链表，而且规模（长度）比原来这条链表小，这就叫规模更小，结构相同的子问题。
我们可以把原先的
head 指针移动到后面这一段链表的开头，然后继续递归调用 reverseKGroup(head, 2)：
所以这里可以使用递归的方式处理大循环，内部可以使用一个迭代的方式实现反转前 N 个节点。
代码如下：
class Solution { public ListNode reverseKGroup(ListNode head, int k) { if (head == null) return null; // 区间 [a, b) 包含 k 个待反转元素 ListNode a, b; a = b = head; for (int i = 0; i < k; i++) { // 不足 k 个，不需要反转了 if (b == null) return head; b = b.next; } // 反转前 k 个元素 ListNode newHead = reverseN(a, k); // 此时 b 指向下一组待反转的头结点 // 递归反转后续链表并连接起来 a.next = reverseKGroup(b, k); return newHead; } // 上文实现的反转前 N 个节点的函数 ListNode reverseN(ListNode head, int n) { if (head == null || head.next == null) { return head; } ListNode pre, cur, nxt; pre = null; cur = head; nxt = head.next; while (n > 0) { cur.next = pre; pre = cur; cur = nxt; if (nxt != null) { nxt = nxt.next; } n--; } head.next = cur; return pre; } }
递归总结：不要跳进递归，而是利用明确的定义来实现算法逻辑。