LeetCode-Book 图解 LCR 123 图书整理 I剑指 Offer 06链表倒序输出的递归与辅助栈两种解法全解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读LCR 123. 图书整理 I即《剑指 Offer 06. 从尾到头打印链表》是 LeetCode-Book 仓库中 leetbook_ioa 路线图的经典入门题考察的是单向链表只能从前向后遍历却要求从尾到头输出这一核心矛盾。本文以仓库文档 LCR 123. 图书整理 I.md 为主体结合仓库中 Python / Java / C 三套可运行的解题代码与公共链表数据结构完整讲解递归法与辅助栈法两种解法的流程、代码与复杂度帮助你掌握逆序输出链表这一类问题的通用套路并能直接在本地运行验证。一、题目背景与题意提炼本题是《剑指 Offer第 2 版》第 6 题在 LeetCode LCR精选题目体系下的对应题目。仓库内与本题同源的专题文档为 剑指 Offer 06. 从尾到头打印链表.md两份文档共享同一套算法思想与代码。题意可以概括为给定单链表的头节点head将链表各节点的值从尾到头依次存入数组并返回。函数签名为reverseBookList(head)。为什么这道题值得单独拎出来讲因为单链表是一种单向顺序访问的数据结构节点间只有next指针无法直接从尾部反向遍历。而题目要求倒序输出天然与先访问的节点最后输出这一先入后出LIFO语义契合因此既可以用递归系统栈天然具备 LIFO 特性也可以用显式辅助栈来求解。这两条路线正是本文的核心。二、方法一递归法先递推到尾回溯时收集2.1 算法流程递归法的思路非常直观先一路递推到链表末端再在回溯返回的过程中依次收集节点值从而得到倒序结果。终止条件当head NoneC 中为nullptr时代表已经越过链表尾节点此时返回空列表递推工作访问下一节点head.next回溯阶段Python返回当前 list 当前节点值 [head.val]即把子问题的倒序结果拼接上当前节点值Java / C将当前节点值head.val加入列表tmp等回溯全部结束后tmp中即是从尾到头的顺序。2.2 代码实现Python / Java / C原文档给出了三份可直接提交的解法代码完整继承如下# Python class Solution: def reverseBookList(self, head: Optional[ListNode]) - List[int]: return self.reverseBookList(head.next) [head.val] if head else []// Java class Solution { ArrayListInteger tmp new ArrayListInteger(); public int[] reverseBookList(ListNode head) { recur(head); int[] res new int[tmp.size()]; for(int i 0; i res.length; i) res[i] tmp.get(i); return res; } void recur(ListNode head) { if(head null) return; recur(head.next); tmp.add(head.val); } }// C class Solution { public: vectorint reverseBookList(ListNode* head) { recur(head); return res; } private: vectorint res; void recur(ListNode* head) { if(head nullptr) return; recur(head-next); res.push_back(head-val); } };实现细节值得注意Python 一行式写法self.reverseBookList(head.next) [head.val] if head else []将终止条件 递推 回溯收集压缩在一条表达式里而 Java / C 由于数组长度不可变无法在回溯时直接 append 到定长数组因此先用ArrayList/vector收集再转为数组返回。2.3 复杂度分析时间复杂度 $O(N)$每个节点恰好被递归访问一次递归调用共 $N$ 次空间复杂度 $O(N)$递归不是尾递归系统调用栈需要为每一层调用保存现场最深时栈深为链表长度 $N$。需要特别提醒当链表非常长例如十万级以上时递归法有栈溢出的风险这也是工业代码中更倾向于使用显式栈或迭代的原因之一。三、方法二辅助栈法入栈逆序出栈还原3.1 算法流程既然单链表只能从前至后访问节点而题目要求倒序输出这种先入后出的需求交给栈来处理再合适不过入栈遍历链表将各节点值依次push入栈出栈将各节点值依次pop出栈存储于结果数组并返回。原文档特别说明图解以 Java 代码为例Python 无需把stack再转移到res而是利用切片stack[::-1]直接返回倒序数组。3.2 代码实现Python / Java / C# Python class Solution: def reverseBookList(self, head: ListNode) - List[int]: stack [] while head: stack.append(head.val) head head.next return stack[::-1]// Java class Solution { public int[] reverseBookList(ListNode head) { LinkedListInteger stack new LinkedListInteger(); while(head ! null) { stack.addLast(head.val); head head.next; } int[] res new int[stack.size()]; for(int i 0; i res.length; i) res[i] stack.removeLast(); return res; } }// C class Solution { public: vectorint reverseBookList(ListNode* head) { stackint stk; while(head ! nullptr) { stk.push(head-val); head head-next; } vectorint res; while(!stk.empty()) { res.push_back(stk.top()); stk.pop(); } return res; } };其中 Java 使用LinkedList模拟栈addLast入栈、removeLast出栈C 直接使用标准库容器适配器std::stack。由于 Java 数组长度不可变仍需要先将出栈元素放入定长数组再返回。3.3 复杂度分析时间复杂度 $O(N)$入栈、出栈各遍历一次总耗时 $O(N)$空间复杂度 $O(N)$辅助栈stack以及 Java/C 中的结果数组res共使用 $O(N)$ 的额外空间。四、仓库源码佐证可运行的三语言实现与公共链表结构LeetCode-Book 仓库不仅给出解题思路还在sword_for_offer/codes/下提供了可本地运行的 Python / Java / C 工程化代码并配有驱动用例方便验证算法正确性。4.1 Python 实现与测试用例递归解法 sfo_06_s1.py辅助栈解法 sfo_06_s2.py两文件均以剑指 Offer 版本的reversePrint命名实现与 LCR 123 的reverseBookList逻辑完全一致并内置了驱动代码head list_to_linked_list([1, 3, 2]) # 由数组构造链表1 - 3 - 2 slt Solution() res slt.reversePrint(head) print(res) # 输出 [2, 3, 1]运行后输出的[2, 3, 1]即为链表1 - 3 - 2的倒序节点值可直接对照验证两种解法的正确性。4.2 公共链表数据结构三语言对照三种语言的实现都依赖仓库include/目录下统一的链表节点定义与构造工具这也解释了为什么各题代码能保持结构一致Pythonlinked_list.py 定义ListNode类并提供list_to_linked_list(arr)由数组构造链表、linked_list_to_list(head)将链表序列化为数组、get_list_node(head, val)按值定位节点JavaListNode.java 定义ListNode类提供静态方法arrToLinkedList(int[] arr)由数组构造链表CListNode.hpp 定义struct ListNode提供vectorToLinkedList(vectorint list)由 vector 构造链表。从源码结构可以推断仓库在组织上采用公共数据结构 每题独立解法 驱动测试的标准化布局每个题目目录下放置对应语言的s1/s2等不同解法文件便于横向对比多种思路如本仓库中 sfo_06 目录同时存在递归与辅助栈两个版本。五、两种方法对比与选型建议维度方法一递归方法二辅助栈核心思想系统栈天然 LIFO回溯时收集显式栈先入后出出栈还原顺序时间复杂度$O(N)$$O(N)$空间复杂度$O(N)$递归栈深$O(N)$辅助栈代码简洁度Python 可一行实现流程直观、无栈溢出风险适用场景链表较短、追求简洁链表较长、需避免栈溢出两条路线的共同本质是利用栈系统栈或显式栈的后进先出特性抵消单链表只能单向遍历的限制。相比递归显式辅助栈不依赖调用栈深度在超长链表场景下更稳健而递归写法在本题中代码更短、更易在面试中快速表达思路。两者时间复杂度与空间复杂度均为 $O(N)$选型时主要权衡代码简洁性与运行健壮性。六、延伸思考掌握了链表倒序输出后可以继续在 LeetCode-Book 仓库中巩固同类链表基础题形成知识闭环LCR 136. 删除链表节点.md 与 剑指 Offer 18. 删除链表的节点.md掌握链表节点的增删改与哨兵节点技巧LCR 141. 训练计划 III.md链表的反转是逆序输出问题的进阶版剑指 Offer 24. 反转链表.md迭代与递归两种反转实现进一步理解链表指针操作。此外逆向思考本题的对称问题——正序遍历并原地收集——恰好对应仓库中的 LCR 123. 图书整理 II.md用队列实现先进先出的正序整理一逆一正两者对照阅读可以更完整地建立链表遍历与数据结构选型的直觉。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 图解 LCR 123 图书整理 I（剑指 Offer 06）：链表倒序输出的递归与辅助栈两种解法全解
LeetCode-Book 图解 LCR 123 图书整理 I剑指 Offer 06链表倒序输出的递归与辅助栈两种解法全解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读LCR 123. 图书整理 I即《剑指 Offer 06. 从尾到头打印链表》是 LeetCode-Book 仓库中 leetbook_ioa 路线图的经典入门题考察的是单向链表只能从前向后遍历却要求从尾到头输出这一核心矛盾。本文以仓库文档 LCR 123. 图书整理 I.md 为主体结合仓库中 Python / Java / C 三套可运行的解题代码与公共链表数据结构完整讲解递归法与辅助栈法两种解法的流程、代码与复杂度帮助你掌握逆序输出链表这一类问题的通用套路并能直接在本地运行验证。一、题目背景与题意提炼本题是《剑指 Offer第 2 版》第 6 题在 LeetCode LCR精选题目体系下的对应题目。仓库内与本题同源的专题文档为 剑指 Offer 06. 从尾到头打印链表.md两份文档共享同一套算法思想与代码。题意可以概括为给定单链表的头节点head将链表各节点的值从尾到头依次存入数组并返回。函数签名为reverseBookList(head)。为什么这道题值得单独拎出来讲因为单链表是一种单向顺序访问的数据结构节点间只有next指针无法直接从尾部反向遍历。而题目要求倒序输出天然与先访问的节点最后输出这一先入后出LIFO语义契合因此既可以用递归系统栈天然具备 LIFO 特性也可以用显式辅助栈来求解。这两条路线正是本文的核心。二、方法一递归法先递推到尾回溯时收集2.1 算法流程递归法的思路非常直观先一路递推到链表末端再在回溯返回的过程中依次收集节点值从而得到倒序结果。终止条件当head NoneC 中为nullptr时代表已经越过链表尾节点此时返回空列表递推工作访问下一节点head.next回溯阶段Python返回当前 list 当前节点值 [head.val]即把子问题的倒序结果拼接上当前节点值Java / C将当前节点值head.val加入列表tmp等回溯全部结束后tmp中即是从尾到头的顺序。2.2 代码实现Python / Java / C原文档给出了三份可直接提交的解法代码完整继承如下# Python class Solution: def reverseBookList(self, head: Optional[ListNode]) - List[int]: return self.reverseBookList(head.next) [head.val] if head else []// Java class Solution { ArrayListInteger tmp new ArrayListInteger(); public int[] reverseBookList(ListNode head) { recur(head); int[] res new int[tmp.size()]; for(int i 0; i res.length; i) res[i] tmp.get(i); return res; } void recur(ListNode head) { if(head null) return; recur(head.next); tmp.add(head.val); } }// C class Solution { public: vectorint reverseBookList(ListNode* head) { recur(head); return res; } private: vectorint res; void recur(ListNode* head) { if(head nullptr) return; recur(head-next); res.push_back(head-val); } };实现细节值得注意Python 一行式写法self.reverseBookList(head.next) [head.val] if head else []将终止条件 递推 回溯收集压缩在一条表达式里而 Java / C 由于数组长度不可变无法在回溯时直接 append 到定长数组因此先用ArrayList/vector收集再转为数组返回。2.3 复杂度分析时间复杂度 $O(N)$每个节点恰好被递归访问一次递归调用共 $N$ 次空间复杂度 $O(N)$递归不是尾递归系统调用栈需要为每一层调用保存现场最深时栈深为链表长度 $N$。需要特别提醒当链表非常长例如十万级以上时递归法有栈溢出的风险这也是工业代码中更倾向于使用显式栈或迭代的原因之一。三、方法二辅助栈法入栈逆序出栈还原3.1 算法流程既然单链表只能从前至后访问节点而题目要求倒序输出这种先入后出的需求交给栈来处理再合适不过入栈遍历链表将各节点值依次push入栈出栈将各节点值依次pop出栈存储于结果数组并返回。原文档特别说明图解以 Java 代码为例Python 无需把stack再转移到res而是利用切片stack[::-1]直接返回倒序数组。3.2 代码实现Python / Java / C# Python class Solution: def reverseBookList(self, head: ListNode) - List[int]: stack [] while head: stack.append(head.val) head head.next return stack[::-1]// Java class Solution { public int[] reverseBookList(ListNode head) { LinkedListInteger stack new LinkedListInteger(); while(head ! null) { stack.addLast(head.val); head head.next; } int[] res new int[stack.size()]; for(int i 0; i res.length; i) res[i] stack.removeLast(); return res; } }// C class Solution { public: vectorint reverseBookList(ListNode* head) { stackint stk; while(head ! nullptr) { stk.push(head-val); head head-next; } vectorint res; while(!stk.empty()) { res.push_back(stk.top()); stk.pop(); } return res; } };其中 Java 使用LinkedList模拟栈addLast入栈、removeLast出栈C 直接使用标准库容器适配器std::stack。由于 Java 数组长度不可变仍需要先将出栈元素放入定长数组再返回。3.3 复杂度分析时间复杂度 $O(N)$入栈、出栈各遍历一次总耗时 $O(N)$空间复杂度 $O(N)$辅助栈stack以及 Java/C 中的结果数组res共使用 $O(N)$ 的额外空间。四、仓库源码佐证可运行的三语言实现与公共链表结构LeetCode-Book 仓库不仅给出解题思路还在sword_for_offer/codes/下提供了可本地运行的 Python / Java / C 工程化代码并配有驱动用例方便验证算法正确性。4.1 Python 实现与测试用例递归解法 sfo_06_s1.py辅助栈解法 sfo_06_s2.py两文件均以剑指 Offer 版本的reversePrint命名实现与 LCR 123 的reverseBookList逻辑完全一致并内置了驱动代码head list_to_linked_list([1, 3, 2]) # 由数组构造链表1 - 3 - 2 slt Solution() res slt.reversePrint(head) print(res) # 输出 [2, 3, 1]运行后输出的[2, 3, 1]即为链表1 - 3 - 2的倒序节点值可直接对照验证两种解法的正确性。4.2 公共链表数据结构三语言对照三种语言的实现都依赖仓库include/目录下统一的链表节点定义与构造工具这也解释了为什么各题代码能保持结构一致Pythonlinked_list.py 定义ListNode类并提供list_to_linked_list(arr)由数组构造链表、linked_list_to_list(head)将链表序列化为数组、get_list_node(head, val)按值定位节点JavaListNode.java 定义ListNode类提供静态方法arrToLinkedList(int[] arr)由数组构造链表CListNode.hpp 定义struct ListNode提供vectorToLinkedList(vectorint list)由 vector 构造链表。从源码结构可以推断仓库在组织上采用公共数据结构 每题独立解法 驱动测试的标准化布局每个题目目录下放置对应语言的s1/s2等不同解法文件便于横向对比多种思路如本仓库中 sfo_06 目录同时存在递归与辅助栈两个版本。五、两种方法对比与选型建议维度方法一递归方法二辅助栈核心思想系统栈天然 LIFO回溯时收集显式栈先入后出出栈还原顺序时间复杂度$O(N)$$O(N)$空间复杂度$O(N)$递归栈深$O(N)$辅助栈代码简洁度Python 可一行实现流程直观、无栈溢出风险适用场景链表较短、追求简洁链表较长、需避免栈溢出两条路线的共同本质是利用栈系统栈或显式栈的后进先出特性抵消单链表只能单向遍历的限制。相比递归显式辅助栈不依赖调用栈深度在超长链表场景下更稳健而递归写法在本题中代码更短、更易在面试中快速表达思路。两者时间复杂度与空间复杂度均为 $O(N)$选型时主要权衡代码简洁性与运行健壮性。六、延伸思考掌握了链表倒序输出后可以继续在 LeetCode-Book 仓库中巩固同类链表基础题形成知识闭环LCR 136. 删除链表节点.md 与 剑指 Offer 18. 删除链表的节点.md掌握链表节点的增删改与哨兵节点技巧LCR 141. 训练计划 III.md链表的反转是逆序输出问题的进阶版剑指 Offer 24. 反转链表.md迭代与递归两种反转实现进一步理解链表指针操作。此外逆向思考本题的对称问题——正序遍历并原地收集——恰好对应仓库中的 LCR 123. 图书整理 II.md用队列实现先进先出的正序整理一逆一正两者对照阅读可以更完整地建立链表遍历与数据结构选型的直觉。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考