力扣Hoot100-反转链表

LeetCode 刷题反转链表：递归解法（简洁优雅的 O (n) 实现）

反转链表是链表类最基础也最核心的面试题，递归解法以「代码极简、逻辑优雅」著称，是面试中展示递归思维的经典案例。本文详解反转链表的尾递归解法，从思路到代码逐行拆解，帮你彻底理解递归反转的核心逻辑。

一、题目描述

反转单链表给你单链表的头节点head，请你反转链表，并返回反转后的链表的头节点。

示例

输入：1 -> 2 -> 3 -> 4 -> 5 -> null输出：5 -> 4 -> 3 -> 2 -> 1 -> null

链表节点定义

java

运行

/** * 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; } * } */

二、解题思路：尾递归反转（核心）

递归的核心是「拆解问题 + 终止条件」，反转链表的尾递归思路可总结为：

1. 问题拆解：反转以cur为当前节点的链表，等价于「先反转cur.next的链表，再将cur的next指向前驱节点pre」；
2. 终止条件：当cur == null时，说明已遍历到链表末尾，此时pre就是反转后的新头节点；
3. 递归过程：用temp暂存cur.next（防止链表断裂），将cur.next指向pre（完成当前节点的反转），再递归处理temp（下一个节点）和cur（新的前驱节点）。

思路可视化（以 1->2->3 为例）

plaintext

初始：cur=1, pre=null 1. 暂存 temp=cur.next=2 → cur.next=pre=null → 递归处理(temp=2, pre=1) 2. 暂存 temp=cur.next=3 → cur.next=pre=1 → 递归处理(temp=3, pre=2) 3. 暂存 temp=cur.next=null → cur.next=pre=2 → 递归处理(temp=null, pre=3) 4. cur=null，返回 pre=3（新头节点） 最终链表：3->2->1->null

三、完整代码实现

class Solution { // 主方法：调用递归函数，初始当前节点为head，前驱节点为null public ListNode reverseList(ListNode head) { return reverse(head, null); } // 递归函数：参数为当前节点cur、前驱节点pre public ListNode reverse(ListNode cur, ListNode pre) { // 终止条件：cur为null，返回pre（反转后的新头节点） if (cur == null) { return pre; } // 1. 暂存cur.next，防止链表断裂 ListNode temp = cur.next; // 2. 反转当前节点：cur的next指向pre cur.next = pre; // 3. 递归处理下一个节点（temp），前驱节点更新为cur return reverse(temp, cur); } }