逆序打印不可变链表技巧(力扣1265)

力扣第 1265 题 “逆序打印不可变链表” 要求在不修改链表结构、且只能使用给定接口getNext()和getValue()的前提下逆序打印一个不可变链表中所有节点的值 。问题解构核心约束不可变链表链表节点本身不可修改没有next指针域只能通过ImmutableListNode接口提供的方法访问。给定接口void printValue()打印当前节点的值。ImmutableListNode* getNext()返回指向下一个节点的指针。如果当前节点是最后一个节点则返回nullptr。目标逆序打印链表所有节点的值。限制不能修改链表结构不能使用额外的数据结构如数组存储所有节点值后再逆序输出除非题目允许但通常空间复杂度有要求。输入输出输入一个ImmutableListNode类型的指针指向链表的头节点。输出逆序打印每个节点的值通常通过调用节点的printValue()方法实现。关键挑战由于链表是单向的且只能向前遍历要“先访问后打印”以实现逆序必须借助某种机制来“记住”之前访问过的节点或延迟打印操作。方案推演与C实现解决此问题的核心思路是利用递归或栈的“后进先出”LIFO特性实现访问顺序与打印顺序的相反。以下是两种主要的C实现方法。方法一递归隐式栈递归在函数调用时会隐式地使用系统栈来保存每一层的状态包括当前节点指针。当递归到链表末尾基线条件开始返回时再依次执行打印操作自然实现了逆序。算法思路基线条件如果当前节点为nullptr直接返回。递归步骤先递归调用函数处理当前节点的下一个节点head-getNext()。打印操作在递归调用返回后再打印当前节点的值head-printValue()。C 实现/** * // This is the ImmutableListNodes API interface. * // You should not implement it, or speculate about its implementation. * class ImmutableListNode { * public: * void printValue(); // print the value of the node. * ImmutableListNode* getNext(); // return the next node. * }; */ class Solution { public: void printLinkedListInReverse(ImmutableListNode* head) { // 基线条件空节点则返回 if (head nullptr) { return; } // 递归处理下一个节点 printLinkedListInReverse(head-getNext()); // 递归返回后打印当前节点实现了逆序 head-printValue(); } };时间复杂度O(n)其中 n 为链表长度。每个节点被访问一次。空间复杂度O(n)递归调用栈的深度等于链表长度。这是最简洁直观的解法 。方法二显式栈迭代显式地使用一个栈Stack数据结构来存储节点指针模拟递归的过程。算法思路遍历链表将所有节点指针依次压入栈中。遍历完成后依次从栈顶弹出节点并打印其值。由于栈的LIFO特性后进栈的节点即原链表中靠后的节点会先被弹出打印。C 实现class Solution { public: void printLinkedListInReverse(ImmutableListNode* head) { stackImmutableListNode* nodeStack; // 第一步遍历链表所有节点指针入栈 ImmutableListNode* curr head; while (curr ! nullptr) { nodeStack.push(curr); curr curr-getNext(); } // 第二步从栈中弹出节点并逆序打印 while (!nodeStack.empty()) { ImmutableListNode* node nodeStack.top(); nodeStack.pop(); node-printValue(); // 打印节点值 } } };时间复杂度O(n)遍历链表一次弹出栈一次。空间复杂度O(n)栈需要存储所有节点指针。方法对比与选择特性递归解法显式栈解法代码简洁性更简洁逻辑清晰代码量少。相对繁琐需要显式管理栈数据结构。空间复杂度O(n)使用系统调用栈。O(n)使用自己维护的栈。适用场景链表长度不是特别大且系统栈深度允许的情况下首选。当链表可能非常长存在递归深度限制栈溢出风险时更安全。控制与调试依赖系统栈调试时调用栈信息直观。栈操作显式对内存使用和控制更直接。选择建议在力扣等编程题环境中只要链表长度在合理范围内通常默认递归深度足够递归解法是首选因为它最贴合“逆序”的逻辑本质且代码极其简洁 。只有在明确担心递归深度可能导致栈溢出时才使用显式栈的迭代解法。扩展空间复杂度 O(1) 但时间复杂度 O(n²) 的解法如果题目对空间复杂度有严格限制要求O(1)可以牺牲时间。思路是对于每个位置 i都从头遍历链表找到倒数第 i 个节点并打印。这需要双层循环。C 实现 (O(1) 空间, O(n²) 时间)class Solution { public: void printLinkedListInReverse(ImmutableListNode* head) { // 首先获取链表长度 int length 0; ImmutableListNode* countPtr head; while (countPtr ! nullptr) { length; countPtr countPtr-getNext(); } // 从最后一个位置开始依次寻找并打印每个节点 for (int i length; i 0; --i) { ImmutableListNode* curr head; // 找到正数第 i 个节点即倒数第 length-i1 个节点这里简化循环从后往前 // 更直接的方式找倒数第 i 个节点等效于走 length - i 步 for (int j 1; j i; j) { // 找到第 i 个节点需要移动 i-1 次 curr curr-getNext(); } curr-printValue(); } } };时间复杂度O(n²)。获取长度 O(n)外层循环 O(n)内层寻找节点平均 O(n/2)故总体为 O(n²)。空间复杂度O(1)只使用了几个固定变量。适用性仅当内存极度受限且可以接受平方级时间复杂度时使用。在实际面试或竞赛中递归或显式栈解法更受认可。总结与关联思考核心思想逆序打印不可变链表的核心是利用栈无论是系统调用栈还是显式栈的LIFO特性将“先访问后处理”的顺序颠倒为“先递归/入栈后返回/出栈时处理”。C实现要点递归基线条件判断空指针递归调用getNext()返回后调用printValue()。显式栈使用std::stackImmutableListNode*先遍历压栈再循环弹栈打印。关联题目模式此题为链表逆序访问的经典问题其变种或类似模式包括逆序输出链表节点值本题。判断链表是否回文结合快慢指针找到中点然后逆序后半部分进行比较。链表的后序遍历式操作先处理子问题再处理当前节点。工程考虑在真实C工程中若链表极长需警惕递归的栈溢出风险通常默认栈空间为几MB。此时应使用显式栈的迭代版本或考虑其他非栈的线性算法如先复制到可变数据结构但可能违反“不可变”约束。因此对于力扣1265题在C中最推荐使用递归解法它完美契合题目要求代码简洁清晰展示了递归在解决此类“反向操作”问题上的优势 。参考来源LeetCode-Python-1265. 逆序打印不可变链表 递归 栈