反转链表
给你单链表的头节点 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），然后利用子问题的解构建原问题的解。
应用于链表反转
对于链表反转问题，我们可以这样思考：
基本情况：当链表为空或只有一个节点时，反转后的链表就是它本身。
递归步骤：假设我们已经能够反转除第一个节点外的剩余链表，然后只需要将第一个节点连接到已反转链表的末尾。
3. 代码解析
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
（继续处理下一个节点）
示例演示（链表 1→2→3→null）
最终返回prev=3，即新链表的头节点。
完整代码
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=1，不需要反转，直接返回原链表
创建虚拟头节点dummy：用于简化操作，最终返回dummy.next
遍历链表：每次处理一组K个节点
检查剩余节点是否足够K个：
从当前head开始向后遍历k-1次
如果中途遇到null，说明剩余节点不足k个
处理两种情况：
如果剩余节点足够k个：反转这k个节点
如果不足k个：保持这组节点顺序不变
将处理后的子链表连接到结果链表
关键方法解析
1.
reverseKGroup方法dummy节点：作为结果链表的虚拟头节点
cur指针：始终指向结果链表的末尾
外层while循环：遍历原始链表
内层while循环：检查剩余节点是否足够k个
flag标志：标记是否成功找到k个节点
2.
doReverse方法反转从head开始的k个节点
使用迭代法反转：
维护newHead作为反转后的头节点
逐个节点反转指针方向
每次处理一个节点，k减1
代码执行流程示例
以链表1→2→3→4→5，k=3为例：
第一组1→2→3：
检查足够3个节点
反转得到3→2→1
连接到dummy后面
第二组4→5：
检查发现只有2个节点(<k)
不反转，直接连接到结果链表末尾
最终结果：3→2→1→4→5
完整代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (head != null) {
ListNode start = head;
int n = k;
boolean flag = true;
while (n > 0) {
head = head.next;
if (head == null) {
flag = false;
break;
}
n--;
}
while (cur.next != null) {
cur = cur.next;
}
if (flag) {
cur.next = doReverse(start, k);
} else {
cur.next = start;
}
}
return dummy.next;
}
public ListNode doReverse(ListNode head, int k) {
if (k == 1) {
return head;
}
ListNode cur = head;
ListNode newHead = null;
while (k > 0 && cur != null) {
ListNode next = cur.next;
cur.next = newHead;
newHead = cur;
cur = next;
k--;
}
return newHead;
}
public static void main(String[] args) {
Solution solution = new Solution();
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
ListNode listNode = solution.reverseKGroup(head, 5);
System.out.println();
}
}