【忍者算法】从生活场景理解链表反转：最重要的基础算法｜LeetCode第206题 反转链表
从生活场景理解链表反转：最重要的基础算法为什么这道题如此重要
反转链表看似简单，却是链表操作的基石。就像建房子要先打好地基，做复杂的链表操作前必须深刻理解反转原理。无数高频面试题都建立在这个基础之上：K个一组反转链表、判断回文链表、链表重排序等等。真正理解了反转链表，这些题目就会迎刃而解。
问题描述
LeetCode第206题"反转链表"要求：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
例如：
输入：1 → 2 → 3 → 4 → 5
输出：5 → 4 → 3 → 2 → 1递归解法：从简单说起
递归法虽然不是最优解，但它的思路最容易理解。想象你在玩多米诺骨牌，先把所有骨牌排好，然后从最后一张开始，一张张往回推。
递归的本质
递归反转的核心思想是：
[*]先假设子问题已经解决（后面的链表已经反转完成）
[*]然后解决当前节点如何与已反转部分衔接的问题
就像你要完成一个大项目，不用考虑下属如何完成他们的任务，你只需要考虑如何把大家的工作整合起来。
代码实现和详解
public ListNode reverseList(ListNode head) {
// 基准情况：空链表或只有一个节点时，直接返回
if (head == null || head.next == null) {
return head;
}
// 递归反转子链表，获得新的头节点
// 假设后面的链表已经反转完成，newHead指向反转后的头节点
ListNode newHead = reverseList(head.next);
// 关键步骤：把当前节点接到反转后链表的末尾
// 假设当前是节点2，head.next是节点3
// head.next.next = head 就是让3指向2
head.next.next = head;
head.next = null;// 断开2原来的指向，防止形成环
return newHead;
}迭代解法：追求空间最优
迭代法虽然理解起来较难，但它是空间复杂度最优的解法。让我们通过一个生活场景来深入理解。
通过生活场景理解迭代
想象你是一个体操教练，正在教一排学生做"后滚翻"。每个学生原本都面向前方，你要让他们一个接一个地转身。关键是：每处理一个学生时，要确保：
[*]这个学生不会摔倒（保存next指针）
[*]他能拉住前一个学生的手（指向prev）
[*]准备好扶住下一个学生（移动指针）
代码实现和图解
public ListNode reverseList(ListNode head) {
ListNode prev = null; // 已翻转部分的头节点
ListNode curr = head; // 当前正在处理的节点
while (curr != null) {
// 第1步：记住下一个学生，以免等下找不到他
ListNode nextTemp = curr.next;
// 第2步：让当前学生转身（改变指针指向）
curr.next = prev;
// 第3步：教练和助教往后移动一位
prev = curr; // prev是"助教"，扶着已完成转身的学生
curr = nextTemp; // curr是"教练"，去帮助下一个学生
}
return prev;// prev指向最后一个处理的节点，即新的头节点
}迭代法的过程图解
以1→2→3→4→5为例：
初始状态：
prev = null, curr = 1
null ← 1 → 2 → 3 → 4 → 5
第一次迭代后：
prev = 1, curr = 2
null ← 1 2 → 3 → 4 → 5
第二次迭代后：
prev = 2, curr = 3
null ← 1 ← 2 3 → 4 → 5
最终状态：
null ← 1 ← 2 ← 3 ← 4 ← 5深入理解的关键点
1. 指针操作的本质
每次操作都是在改变一个节点的"指向"。就像改变一个人的视线方向，原本看着前方，现在要回头看。
2. 迭代法的不变量
在任何时刻：
[*]prev指向的是已完成反转的部分
[*]curr指向正在处理的节点
[*]nextTemp保存着待处理的部分
3. 为什么需要三个指针
[*]prev：没有它，就不知道往哪里指
[*]curr：没有它，就不知道现在处理谁
[*]nextTemp：没有它，就会断链找不到后续节点
实战应用
这个基础算法在很多场景中都有应用：
[*]需要倒序处理链表时
[*]需要判断链表是否回文时
[*]需要按组反转链表时
[*]需要重排链表时
小结
掌握链表反转需要：
[*]理解递归和迭代两种思路的本质
[*]深入理解指针操作的含义
[*]反复练习直至形成肌肉记忆
[*]学会用生活场景类比，加深理解
建议：每天默写一遍这道题，直到闭着眼睛也能写对。因为它是链表操作中最基础也是最关键的操作，掌握了它，其他链表问题都会变得容易很多！
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]