反向输出一个链表

### 反向输出链表的实现 #### 使用栈结构反向输出单链表 可以借助栈这种数据结构来实现链表的反向输出。由于栈具有后进先出的特点，因此可以通过遍历链表并将节点压入栈中，最后再依次弹出来完成反向操作。 以下是基于 C++ 的代码示例： ```cpp #include <iostream> #include <stack> using namespace std; struct Node { int value; Node* next; Node(int val) : value(val), next(nullptr) {} }; void reversePrintUsingStack(Node* head) { stack<Node*> nodeStack; Node* current = head; // 将所有节点压入栈中 while (current != nullptr) { nodeStack.push(current); current = current->next; } // 从栈顶开始打印节点值 while (!nodeStack.empty()) { cout << nodeStack.top()->value << " "; nodeStack.pop(); } } int main() { Node* d = new Node(8); Node* c = new Node(7, d); Node* b = new Node(6, c); Node* a = new Node(5, b); cout << "Original List: "; Node* temp = a; while (temp != nullptr) { cout << temp->value << "\t"; temp = temp->next; } cout << "\nReversed Output Using Stack: "; reversePrintUsingStack(a); return 0; } ``` 这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)[^2]。 --- #### 修改指针方向反转链表 另一种方式是直接修改链表中的 `next` 指针的方向，从而达到反转整个链表的效果。这种方式不需要额外的空间开销。 下面是基于 C++ 实现的代码示例： ```cpp Node* reverseListIteratively(Node* head) { Node* prev = nullptr; Node* curr = head; Node* nextTemp = nullptr; while (curr != nullptr) { nextTemp = curr->next; // 保存下一个节点 curr->next = prev; // 当前节点指向其上一节点 prev = curr; // 移动到下一位置 curr = nextTemp; } return prev; // 返回新的头结点 } int main() { Node* d = new Node(8); Node* c = new Node(7, d); Node* b = new Node(6, c); Node* a = new Node(5, b); cout << "Original List: "; Node* temp = a; while (temp != nullptr) { cout << temp->value << "\t"; temp = temp->next; } cout << "\nAfter Reversing Iteratively: "; Node* reversedHead = reverseListIteratively(a); temp = reversedHead; while (temp != nullptr) { cout << temp->value << "\t"; temp = temp->next; } return 0; } ``` 上述方法通过迭代的方式实现了链表的反转，时间复杂度同样为 O(n)，但空间复杂度仅为 O(1)[^2]。 --- #### Python 中的链表反向输出 在 Python 中也可以轻松实现链表的反向输出。下面是一个简单的例子，展示了如何使用递归或者栈的方式来处理这个问题。 ##### 方法一：递归法 递归是一种非常优雅的方式来实现链表的反向输出。它会一直深入到最后一个节点，然后再逐层返回并打印节点值。 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_print_recursive(head): if head is None: return reverse_print_recursive(head.next) print(head.val, end=" ") # 测试用例 a = ListNode(5) b = ListNode(6, a) c = ListNode(7, b) d = ListNode(8, c) print("Original List:") temp = d while temp: print(temp.val, end=" ") temp = temp.next print("\nReverse Print via Recursion:") reverse_print_recursive(d) ``` ##### 方法二：栈法 类似于前面提到的 C++ 版本，Python 同样可以用栈来辅助完成这一任务。 ```python def reverse_print_stack(head): stack = [] current = head # 压栈过程 while current: stack.append(current.val) current = current.next # 出栈过程 while stack: print(stack.pop(), end=" ") # 测试用例同上 print("\nReverse Print via Stack:") reverse_print_stack(d) ``` 这两种方法都可以有效地实现链表的反向输出[^3]。 --- ### 性能比较 - **栈方法**适合于不想改变原链表结构的情况，但它需要额外的存储空间。 - **迭代反转方法**适用于那些允许破坏原始链表的应用场景，并且它的内存效率更高。 - **递归方法**则提供了一种简洁明了的解决方案，但在极端情况下可能会因为调用堆栈过深而导致溢出错误。 --- 问题