206.反转链表
给你单链表的头节点 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
反转链表通常有两种方法：迭代法和递归法。
迭代法（双指针）
假设原来的链表是1->2->3->4->5->null，反转后变成null<-1<-2<-3<-4<-5。那在迭代的时候，初始状态应该是prev=null，current=head。然后循环处理每个节点：
在循环中，首先保存当前节点的下一个节点nextTemp，然后把当前节点的next指向prev。接着prev移动到current的位置，current移动到nextTemp的位置。直到current为null，此时prev就是新的头节点。
实现代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode current = head;
ListNode prev = null;
while (current != null) {
ListNode nextTemp = current.next; // 保存下一个节点
current.next = prev; /// 反转指针
prev = current; // 前移prev
current = nextTemp; // 前移current
}
return prev; // prev即为新链表的头结点
}
}步骤解释：
初始化指针：使用两个指针
prev和current，初始时prev为null，current指向头节点head。遍历链表：在
current不为null时循环处理每个节点。保存下一个节点：临时存储
current.next到nextTemp，防止反转指针后丢失后续节点。反转指针：将当前节点
current的next指向prev，完成当前节点的反转。移动指针：将
prev移动到当前current的位置，current移动到之前保存的nextTemp位置。
返回新头节点：当循环结束时，
current为null，prev指向原链表的最后一个节点，即反转后的新头节点。
递归法
递归方法的步骤如下：
- 递归终止条件：当前节点为空或下一个子节点为空，返回当前节点
- 递归反转后续链表，得到反转后的头结点
- 将当前节点的下一个节点的next指向当前节点，形成反转
- 将当前节点的next设为null，断开原来的连接
- 返回反转后的头结点
实现代码
class Solution {
public ListNode reverseList(ListNode head) {
// 递归法
// 递归终止条件，空链表或单链表无需反转
if (head == null || head.next == null) {
return head;
}
// 递归反转后续链表，得到新头结点
ListNode newHead = reverseList(head.next);
// 调整指针方向，将当前节点的下一个节点的next指向自己
head.next.next = head;
// 断开当前节点的原指向，防止循环
head.next = null;
// 返回新头结点
return newHead;
}
}示例分析
1. 递归调用栈展开
递归从头部节点 1 开始，逐层深入，直到链表末尾的节点 5。以下是调用栈的展开过程：
reverseList(1) → reverseList(2) → reverseList(3) → reverseList(4) → reverseList(5)
终止条件触发：当调用 reverseList(5) 时，5.next == null，直接返回 5（此时 newHead = 5）。
2. 递归回溯与指针调整
递归开始逐层回溯，每层处理当前节点并调整指针方向：
层 4（head = 4）
输入链表状态：
4 → 5操作步骤：
收到下层返回的
newHead = 5。调整指针：
4.next.next = 4→5.next = 4（形成5 → 4）。断开原链：
4.next = null（防止4 → 5循环）。
输出链表状态：
5 → 4 → null返回：
newHead = 5
层 3（head = 3）
输入链表状态：
3 → 4 → null（原链未修改时，3.next仍指向4）。操作步骤：
收到下层返回的
newHead = 5。调整指针：
3.next.next = 3→4.next = 3（形成5 → 4 → 3）。断开原链：
3.next = null。
输出链表状态：
5 → 4 → 3 → null返回：
newHead = 5
层 2（head = 2）
输入链表状态：
2 → 3 → null（原链未修改时，2.next指向3）。操作步骤：
收到下层返回的
newHead = 5。调整指针：
2.next.next = 2→3.next = 2（形成5 → 4 → 3 → 2）。断开原链：
2.next = null。
输出链表状态：
5 → 4 → 3 → 2 → null返回：
newHead = 5
层 1（head = 1）
输入链表状态：
1 → 2 → null（原链未修改时，1.next指向2）。操作步骤：
收到下层返回的
newHead = 5。调整指针：
1.next.next = 1→2.next = 1（形成5 → 4 → 3 → 2 → 1）。断开原链：
1.next = null。
输出链表状态：
5 → 4 → 3 → 2 → 1 → null返回：
newHead = 5
总结
递归终止条件：处理到链表末尾时直接返回。
递归分解问题：假设后续链表已反转，只需调整当前节点和下一个节点的指针。
指针操作：通过
head.next.next = head和head.next = null完成局部反转并断开原链。