https://leetcode.cn/problems/reverse-linked-list/description/
一、题目解析
1.1 题意
给定单链表的头节点 head，反转链表，返回反转后的头节点。原链表尾节点变成新头，每个节点的 next 指针反向指向前驱。
原链表：1 → 2 → 3 → null反转后：3 → 2 → 1 → null链表节点定义是标准的 ListNode，有 val 和 next 两个字段。
二、递归解法一：类变量存新头
思路：递归走到链表末尾，用一个类变量 ans 抓住尾节点作为反转后的新头。回溯时逐层翻转指针。
class Solution { // 类变量，存反转后的新头节点（原链表尾节点） private ListNode ans = null; private void reverseListHelp(ListNode head) { // 走到最后一个节点，它就是新头 if (head.next == null) { ans = head; return; } // 先递归到底 reverseListHelp(head.next); // 回溯：让后继节点回头指向自己 head.next.next = head; // 断开自己原来的 next，防止成环 head.next = null; } public ListNode reverseList(ListNode head) { if (head == null) { return null; } reverseListHelp(head); return ans; }}*reverseListHelp 一路沿着 next 往下走，直到 head.next == null，也就是原链表的尾节点。此时把 ans = head，这个引用会跟着对象一路活到方法返回。
回溯时,递归到底后开始逐层返回。假设当前在节点 2，下一层已经处理完节点 3。head.next.next = head 让 3 的 next 指向 2，head.next = null 断开 2 原本指向 3 的指针。每一层只翻转自己和后继的关系，等回溯到第一层时整个链表就反过来了。
三、递归解法二：通过返回值传递新头
思路：不不需要引入类变量，而是让新头通过返回值从底层一路透传上来。
class Solution { public ListNode reverseList(ListNode head) { // 空链表或走到尾节点，直接返回（它就是新头） if (head == null || head.next == null) { return head; } // 递归反转后续链表，next 即为反转后的新头 ListNode next = reverseList(head.next); // 让后继节点回头指向自己 head.next.next = head; // 断开原指针 head.next = null; // 把新头原样传回上层 return next; }}返回值是什么。 reverseList 的返回值始终是新链表的头节点（原尾节点）。递归到底时 head.next == null，返回的就是尾节点本身。回溯时每一层拿到下层返回的 next，干完指针翻转的活之后，把 next 原封不动扔回给上层。新头从头到尾不变，只是在递归链上被传递。
和解法一的区别。 解法一把新头存在类变量里，helper 方法返回 void；解法二用返回值透传，省掉一个类变量，代码更短。两版的指针翻转逻辑完全一致：head.next.next = head + head.next = null。
四、栈模拟递归
思路：既然递归的本质是隐式调用栈，那就自己搞一个显式的 Stack，先把所有节点按顺序推进去，再按出栈顺序重新串起来。
class Solution { public ListNode reverseList(ListNode head) { if (head == null) { return null; } Stack<ListNode> stack = new Stack<>(); // 把所有节点依次压栈 while (head != null) { stack.push(head); head = head.next; } // 栈顶是原尾节点，即新头 ListNode ans = stack.pop(); ListNode temp = ans; // 逐个弹出，反向链接 while (!stack.isEmpty()) { ListNode node = stack.pop(); // 清掉弹出节点的 next，避免残留指针 node.next = null; temp.next = node; temp = node; } return ans; }}压栈阶段。 从头到尾遍历链表，每个节点 push 进栈。栈顶是尾节点（最后一个 push），栈底是头节点（第一个 push）。
出栈重建。 先 pop 出栈顶作为新头 ans。之后每次 pop 一个节点，把它的 next 置空（因为原链表中它指向的是前驱节点，不置空会成环），然后将当前尾节点 temp 的 next 指向它，temp 后移。最后栈空时链表重建完毕。
为什么要 node.next = null。 原链表里 node 的 next 指向它的后继。压栈时我们没有改动任何指针，所以弹出重建时必须手动切断原 next，否则链表末尾会指回前面的节点。
五、复杂度分析
| 解法 | 时间 | 空间 |
|---|---|---|
| 递归一 | O(n) | O(n)（递归栈） |
| 递归二 | O(n) | O(n)（递归栈） |
| 栈模拟 | O(n) | O(n)（显式栈） |
三种解法都是 O(n) 时间、O(n) 空间。递归的空间开销是调用栈深度，栈模拟的空间开销是 Stack 的大小，都是 n。
本文由 AgentPlanFlow 生成