// 单链表节点定义
public class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
题目:给定单链表头节点,反转链表,返回新的头节点。
迭代法:
思路:逐个翻转每个节点的next指针
初始状态:
1 → 2 → 3 → 4 → 5 → null
↑
head
过程:
prev = null, curr = head
Step 1: curr=1
next = curr.next = 2
curr.next = prev = null ← 翻转!
prev = curr = 1
curr = next = 2
null ← 1 2 → 3 → 4 → 5 → null
Step 2: curr=2
next = curr.next = 3
curr.next = prev = 1 ← 翻转!
prev = curr = 2
curr = next = 3
null ← 1 ← 2 3 → 4 → 5 → null
Step 3: curr=3
null ← 1 ← 2 ← 3 4 → 5 → null
Step 4: curr=4
null ← 1 ← 2 ← 3 ← 4 5 → null
Step 5: curr=5
null ← 1 ← 2 ← 3 ← 4 ← 5
↑ prev(新head)
curr = null → 结束,返回 prev
// 迭代法
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // 保存后继
curr.next = prev; // 翻转指针
prev = curr; // prev前进
curr = next; // curr前进
}
return prev;
}
// 时间:O(n) 空间:O(1)
递归法:
递归思路:
reverseList(head) 翻转以head开头的链表
子问题:reverseList(head.next) 翻转后续链表
1 → 2 → 3 → 4 → 5 → null
递归到最深层:reverseList(5) → 返回5(新head)
回溯:reverseList(4)
head = 4, head.next = 5
head.next.next = head → 5 → 4(翻转!)
head.next = null → 5 → 4 → null
返回 5
reverseList(3):
5 → 4 → 3 → null
reverseList(2):
5 → 4 → 3 → 2 → null
reverseList(1):
5 → 4 → 3 → 2 → 1 → null
// 递归法
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; // 断开原来的next
return newHead;
}
// 时间:O(n) 空间:O(n)(递归栈)
变体题:
141 - 判断是否有环:
快慢指针法(Floyd龟兔赛跑):
slow 每次走1步
fast 每次走2步
如果无环:fast先到达null → 无环
如果有环:fast在环内追上slow → 有环
图解:
1 → 2 → 3 → 4 → 5 → 6
↑ │
└─────────┘ (4→6→4,有环)
slow: 1 → 2 → 3 → 4 → 5 → 6 → 4 ...
fast: 1 → 3 → 5 → 4 → 6 → 4 ... (fast在4追上slow)
数学证明:
设环长为C,slow进入环后,fast在环内某位置
每一步 fast 比 slow 多走1步
最多 C 步后 fast 追上 slow
// LeetCode 141
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 走1步
fast = fast.next.next; // 走2步
if (slow == fast) return true; // 相遇 → 有环
}
return false; // fast到达null → 无环
}
// 时间:O(n) 空间:O(1)
142 - 找环的入口节点:
阶段1:快慢指针找相遇点
阶段2:一个从head出发,一个从相遇点出发,速度都是1步
→ 再次相遇的节点就是环的入口!
数学推导:
设 head 到环入口距离 = a
环入口到相遇点距离 = b
相遇点到环入口距离 = c
环长 = b + c
slow走了:a + b
fast走了:a + b + k(b + c)(k圈)
fast = 2 * slow:
a + b + k(b + c) = 2(a + b)
a + b + k(b + c) = 2a + 2b
k(b + c) = a + b
k(b + c) - b = a
(k-1)(b+c) + c = a
结论:a = c + (k-1)圈
→ 从head走a步 = 从相遇点走c步 + (k-1)圈 → 一定在环入口相遇!
// LeetCode 142
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
// 阶段1:找相遇点
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 阶段2:找环入口
ListNode p1 = head, p2 = slow;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1; // 环入口
}
}
return null; // 无环
}
// 时间:O(n) 空间:O(1)
变体题:
题目:将两个升序链表合并为一个新的升序链表。
思路:双指针遍历,每次取较小的节点
List1: 1 → 3 → 5 → null
List2: 2 → 4 → 6 → null
用哑节点(dummy)简化头节点处理:
dummy → ?
p1指向1, p2指向2
Step 1: 1 < 2 → dummy.next = 1, p1前进
dummy → 1 → ?
p1指向3, p2指向2
Step 2: 3 > 2 → tail.next = 2, p2前进
dummy → 1 → 2 → ?
p1指向3, p2指向4
Step 3: 3 < 4 → tail.next = 3, p1前进
dummy → 1 → 2 → 3 → ?
p1指向5, p2指向4
...最终:dummy → 1 → 2 → 3 → 4 → 5 → 6
返回 dummy.next
// 迭代法
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1); // 哑节点
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
// 剩余部分直接接上
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
// 时间:O(n+m) 空间:O(1)
// 递归法
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
// 时间:O(n+m) 空间:O(n+m)(递归栈)
变体题:
题目:找到链表的中间节点。如果有两个中间节点,返回第二个。
快慢指针法:
slow走1步,fast走2步
fast到末尾时,slow就在中间
奇数长度:1 → 2 → 3 → 4 → 5
slow: 1 → 2 → 3 → 返回3
fast: 1 → 3 → 5 (null)
偶数长度:1 → 2 → 3 → 4 → 5 → 6
slow: 1 → 2 → 3 → 返回3(第二个中间节点)
fast: 1 → 3 → 5 → null
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 时间:O(n) 空间:O(1)
如果要求返回第一个中间节点(偶数长度时):
// 返回第一个中间节点
public ListNode middleNodeFirst(ListNode head) {
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
// 注意条件不同:判断的是 fast.next 和 fast.next.next
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
题目:删除链表的倒数第n个节点,返回链表头节点。
思路:快慢指针,fast先走n步,然后slow和fast一起走
示例:1 → 2 → 3 → 4 → 5,删除倒数第2个(4)
Step 1: fast先走n=2步
dummy → 1 → 2 → 3 → 4 → 5
slow↑ fast↑
Step 2: slow和fast一起走,直到fast到达末尾
dummy → 1 → 2 → 3 → 4 → 5 → null
slow↑ fast↑
Step 3: slow.next = slow.next.next(删除节点4)
dummy → 1 → 2 → 3 → 4 → 5
slow↑ ↑ 跳过4
结果:1 → 2 → 3 → 5
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head); // 哑节点处理删除头节点的情况
ListNode slow = dummy, fast = dummy;
// fast先走n步(注意:从dummy开始,走n步后fast指向第n个节点)
for (int i = 0; i < n; i++) {
fast = fast.next;
}
// slow和fast一起走,直到fast到达最后一个节点
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
// 删除slow的下一个节点
slow.next = slow.next.next;
return dummy.next;
}
// 时间:O(L) L=链表长度 空间:O(1)
变体题:
┌──────────────────────────────────────────────────────────────┐
│ 链表六大技巧 │
├──────────────────────────────────────────────────────────────┤
│ │
│ 1. 哑节点(Dummy Node) │
│ → 简化头节点的特殊处理(删除/插入头节点时) │
│ → 几乎所有链表题都应该考虑是否需要 │
│ │
│ 2. 快慢指针 │
│ → 找中间节点:fast走2步,slow走1步 │
│ → 检测环:fast走2步,slow走1步,相遇=有环 │
│ → 找倒数第N个:fast先走N步,再一起走 │
│ │
│ 3. 双指针(前后指针) │
│ → 合并有序链表:两个指针各遍历一条链表 │
│ → 交集/差集:两条链表的公共节点 │
│ │
│ 4. 翻转指针 │
│ → 反转链表的核心:curr.next = prev │
│ → 记住三步:保存next → 翻转 → 前进 │
│ │
│ 5. 递归 │
│ → 反转链表、合并链表都有递归写法 │
│ → 思考:子问题是什么?递归返回什么?当前层做什么? │
│ │
│ 6. 画图! │
│ → 链表题最容易出错的是指针操作 │
│ → 每一步画出节点和指针的指向 │
│ → 特别注意:next指针的赋值顺序(先保存再修改) │
│ │
└──────────────────────────────────────────────────────────────┘
Q1: 反转链表的迭代法中,为什么要用next变量保存curr.next?
因为curr.next = prev会修改curr.next,如果不先保存,就无法移动到下一个节点。这是链表操作最常见的坑:修改指针前先保存。
Q2: 快慢指针为什么能检测环?数学上如何证明?
slow走1步,fast走2步,每步fast比slow多走1步。如果有环,fast在环内一定追上slow(因为每步距离缩小1)。如果无环,fast先到null。
Q3: 为什么删除倒数第N个节点需要哑节点?
如果删除的是头节点(倒数第L个,L为链表长度),没有哑节点时需要特殊处理head = head.next。有哑节点时,所有删除操作统一为slow.next = slow.next.next。
Q4: 合并K个有序链表(LeetCode 23)怎么做?
用最小堆(PriorityQueue)。将K个链表的头节点放入堆,每次弹出最小的节点加入结果,然后将该节点的next放入堆。时间O(N log K),N为总节点数,K为链表数。
Q5: 链表题最常见的bug是什么?
(1) 空指针异常:未检查null;(2) 指针修改顺序错误:先改了next导致后续节点丢失;(3) 死循环:链表成环(翻转时忘记断开原来的next);(4) 边界条件:单个节点、空链表、删除头节点。
1. 手动推演反转链表 [1,2,3,4,5] 的迭代过程,画出每一步三个指针的指向。
2. 编写环形链表II的代码,手动推演找环入口的过程(设定具体的环位置)。
3. 合并两个有序链表 [1,3,5] 和 [2,4,6],画出哑节点和两个指针的变化过程。
4. 删除链表 [1,2,3,4,5] 的倒数第2个节点,如果不使用哑节点,代码需要怎么处理边界?
5. 用递归法反转链表 [1,2,3],画出递归调用栈和每一步的链表状态变化。