力扣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; } * } */二、解题思路尾递归反转核心递归的核心是「拆解问题 终止条件」反转链表的尾递归思路可总结为问题拆解反转以cur为当前节点的链表等价于「先反转cur.next的链表再将cur的next指向前驱节点pre」终止条件当cur null时说明已遍历到链表末尾此时pre就是反转后的新头节点递归过程用temp暂存cur.next防止链表断裂将cur.next指向pre完成当前节点的反转再递归处理temp下一个节点和cur新的前驱节点。思路可视化以 1-2-3 为例plaintext初始cur1, prenull 1. 暂存 tempcur.next2 → cur.nextprenull → 递归处理(temp2, pre1) 2. 暂存 tempcur.next3 → cur.nextpre1 → 递归处理(temp3, pre2) 3. 暂存 tempcur.nextnull → cur.nextpre2 → 递归处理(tempnull, pre3) 4. curnull返回 pre3新头节点 最终链表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); } }