当前位置：首页 > news >正文

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

news 2026/5/10 12:23:08

力扣第 1265 题 “逆序打印不可变链表” 要求在不修改链表结构、且只能使用给定接口getNext()和getValue()的前提下，逆序打印一个不可变链表中所有节点的值。

问题解构

核心约束：
- 不可变链表：链表节点本身不可修改，没有next指针域，只能通过ImmutableListNode接口提供的方法访问。
- 给定接口：
  - void printValue()：打印当前节点的值。
  - ImmutableListNode* getNext()：返回指向下一个节点的指针。如果当前节点是最后一个节点，则返回nullptr。
- 目标：逆序打印链表所有节点的值。
- 限制：不能修改链表结构，不能使用额外的数据结构（如数组）存储所有节点值后再逆序输出（除非题目允许，但通常空间复杂度有要求）。
输入输出：
- 输入：一个ImmutableListNode类型的指针，指向链表的头节点。
- 输出：逆序打印每个节点的值（通常通过调用节点的printValue()方法实现）。
关键挑战：由于链表是单向的且只能向前遍历，要“先访问后打印”以实现逆序，必须借助某种机制来“记住”之前访问过的节点或延迟打印操作。

方案推演与C++实现

解决此问题的核心思路是利用递归或栈的“后进先出”（LIFO）特性，实现访问顺序与打印顺序的相反。以下是两种主要的C++实现方法。

方法一：递归（隐式栈）

递归在函数调用时会隐式地使用系统栈来保存每一层的状态（包括当前节点指针）。当递归到链表末尾（基线条件）开始返回时，再依次执行打印操作，自然实现了逆序。

算法思路：

基线条件：如果当前节点为nullptr，直接返回。
递归步骤：先递归调用函数处理当前节点的下一个节点（head->getNext()）。
打印操作：在递归调用返回后，再打印当前节点的值（head->printValue()）。

C++ 实现：

/** * // This is the ImmutableListNode's 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) { stack<ImmutableListNode*> 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-i+1 个节点，这里简化循环从后往前） // 更直接的方式：找倒数第 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::stack<ImmutableListNode*>，先遍历压栈，再循环弹栈打印。
关联题目模式：此题为链表逆序访问的经典问题，其变种或类似模式包括：
- 逆序输出链表节点值（本题）。
- 判断链表是否回文（结合快慢指针找到中点，然后逆序后半部分进行比较）。
- 链表的后序遍历式操作（先处理子问题，再处理当前节点）。
工程考虑：在真实C++工程中，若链表极长，需警惕递归的栈溢出风险（通常默认栈空间为几MB）。此时应使用显式栈的迭代版本，或考虑其他非栈的线性算法（如先复制到可变数据结构，但可能违反“不可变”约束）。