链表简单2 种解法
#206反转链表
反转单链表的 next 方向并返回新的头节点。
#链表#递归
原题
给你单链表的头节点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
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解题主线
- 迭代时必须先保存 next，再修改 current.next，否则会丢失未处理部分。
- 递归返回后让 head.next.next 指回 head，并把 head.next 置 null 断开旧方向。
解法 1：迭代反转
维护 previous、current 和 next，逐条把 next 边反向。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
public class Solution {
static final class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode reverseList(ListNode head) {
ListNode previous = null;
ListNode current = head;
// previous 始终是已反转前缀的头，current 指向未处理后缀
while (current != null) {
// 改写 current.next 前先保存后继，避免丢失未处理链表
ListNode next = current.next;
current.next = previous;
// 两个指针同步前移，扩大已反转前缀
previous = current;
current = next;
}
return previous;
}
}解法 2：递归反转
先反转 head.next 开始的后缀，回溯时把后继指回 head 并切断 head 的旧后继。
-
时间复杂度： O(n)
-
空间复杂度： O(n)（递归栈）
public class Solution {
static final class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode reverseList(ListNode head) {
// 空链表或单节点链表已是反转结果，也是递归终点
if (head == null || head.next == null) return head;
// 先反转后缀，newHead 在回溯过程中始终保持为新头节点
ListNode newHead = reverseList(head.next);
// 让原后继指回当前节点，再切断旧方向以避免形成环
head.next.next = head;
head.next = null;
return newHead;
}
}边界与易错点
- 递归版本若不执行 head.next = null，会在原头部附近形成环。
- 递归深度为 n，超长链表可能导致栈溢出，生产代码通常优先迭代。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
Q206_ReverseList.java