LeetCode - 二叉树的层序遍历 / 轮转数组
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解题思路
递归（尾插法）
递归递归，有递有归。
我们先「递」到链表的末尾节点，作为新链表的头节点。然后在「归」的过程中，一个一个地把节点插在新链表的末尾。
递归的基本思想
递归的核心在于将问题分解为更小的子问题，直到达到基本情况（base case），然后利用子问题的解构建原问题的解。
应用于链表反转
对于链表反转问题，我们可以这样思考：
基本情况：当链表为空或只有一个节点时，反转后的链表就是它本身。
递归步骤：假设我们已经能够反转除第一个节点外的剩余链表，然后只需要将第一个节点连接到已反转链表的末尾。
代码解析
public ListNode reverseList(ListNode head) {
if (head == null) {
return head; // 处理空链表的情况
}
return doReverseList(head); // 调用实际的递归函数
}
public ListNode doReverseList(ListNode head) {
// 基本情况：当前节点是最后一个节点
if (head.next == null) {
return head; // 返回这个节点作为新链表的头
}
// 递归反转剩余链表
ListNode tail = doReverseList(head.next);
// 关键操作：将当前节点连接到已反转链表的末尾
ListNode newHead = head.next; // newHead实际上是原链表的下一个节点
newHead.next = head; // 将当前节点接在已反转链表的后面
head.next = null; // 断开原来的连接，防止循环
return tail; // 返回新链表的头节点（即原链表的尾节点）
}具体步骤说明
终止条件：当
head.next == null时，说明当前节点是最后一个节点，直接返回它作为新链表的头。递归调用：
doReverseList(head.next)会反转从head.next开始的链表，并返回反转后的头节点（即原链表的尾节点）。连接当前节点：
newHead = head.next：获取已反转链表的最后一个节点（即原链表中当前节点的下一个节点）。newHead.next = head：将当前节点接在已反转链表的后面。head.next = null：断开当前节点与原链表的连接，防止循环。
返回结果：最终返回的是原链表的尾节点，即反转后的新链表的头节点。
总结
这种递归解法简洁优雅，但需要注意：
递归深度可能引发栈溢出（对于非常长的链表）。
理解递归的关键在于信任递归函数能正确解决子问题，并专注于当前层的逻辑。
迭代（头插法）
核心思想
像翻书一样，每次只处理当前页（节点），把它的指向从后页改为前页，直到翻完全书（链表）。如果确实理解起来比较抽象，可以硬背下来，代码是比较固定的。
变量作用
prev：记录已反转部分的头节点（初始为null）curr：当前待反转的节点（初始为head）next：临时保存curr的下一个节点
四步操作流程
备份后驱：
next = curr.next
（先记住下一个要处理的节点，避免断链后丢失）反转指针：
curr.next = prev
（将当前节点指向前一个节点，实现反转）移动prev：
prev = curr
（已反转部分的新头变成当前节点）移动curr：
curr = next
（继续处理下一个节点）
示例演示
初始状态：
null [A] → [B] → [C] → null
pre head第1次循环：
next = B（记住B的位置）A.next = null（A指向null）pre = A（已反转部分：A→null）head = B（准备处理B）
null ← [A] [B] → [C] → null
pre head第2次循环：
next = C（记住C的位置）B.next = A（B指向A）pre = B（已反转部分：B→A→null）head = C（准备处理C）
null ← [A] ← [B] [C] → null
pre head第3次循环：
next = null（记住null位置）C.next = B（C指向B）pre = C（已反转部分：C→B→A→null）head = null（处理完成）
null ← [A] ← [B] ← [C]
pre head(null)完整代码
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
while(head!=null){
ListNode next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
提示：
链表中的节点数目为
n1 <= k <= n <= 50000 <= Node.val <= 1000
解题思路
整体思路
将问题分解为两个步骤：
反转当前组：把前k个节点反转
递归处理剩余组：剩余部分继续k个一组反转，并与当前组连接
步骤解析
第1步：检查节点数量
ListNode tail = head;
for (int i = 0; i < k; i++) {
if (tail == null) return head;
tail = tail.next;
}tail从head出发，走k步如果中途遇到null，说明不够k个，不需要反转，直接返回原链表
循环结束后，
tail指向第k+1个节点（下一组的头）
第2步：反转前k个节点
ListNode prev = null;
ListNode curr = head;
for (int i = 0; i < k; i++) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}标准的链表反转，执行k次
结束后：
prev指向原第k个节点（新头）curr指向第k+1个节点（下一组的头）head指向原第1个节点（新尾）
第3步：递归处理后续
head.next = reverseKGroup(curr, k);head现在是反转后的尾节点它的next应该指向「剩余部分反转后的头」
剩余部分从
curr开始，继续k个一组反转
第4步：返回新头
return prev;prev是这一组反转后的头节点也是整个函数的返回值
完整代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 1. 检查是否有足够k个节点
ListNode tail = head;
for (int i = 0; i < k; i++) {
if (tail == null) return head; // 不足k个，直接返回head
tail = tail.next;
}
// 2. 反转前k个节点
ListNode prev = null;
ListNode curr = head;
for (int i = 0; i < k; i++) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 3. 递归处理剩余节点，并连接
head.next = reverseKGroup(curr, k);
// 4. 返回反转后的头节点
return prev;
}
}