c++栈反转链表

### C++ 使用栈反转单链表的实现方法 在C++中，可以借助栈的数据结构来完成单链表的反转。栈是一种后进先出（LIFO, Last In First Out）的数据结构，非常适合用来存储链表中的节点并按相反顺序取出它们。 以下是具体的实现方式： #### 定义链表节点类 为了便于操作，首先定义一个简单的链表节点类 `ListNode`[^1]。 ```cpp struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ``` #### 使用栈反转链表的核心逻辑 通过遍历原始链表并将每个节点压入栈中，然后再依次弹出栈顶元素构建新的链表，从而达到反转的效果[^2]。 下面是完整的代码实现： ```cpp #include <iostream> #include <stack> using namespace std; // 定义链表节点 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; // 函数：使用栈反转链表 ListNode* reverseListUsingStack(ListNode* head) { stack<ListNode*> nodeStack; // 创建一个栈用于存储链表节点 // 将链表中的所有节点压入栈中 ListNode* current = head; while (current != nullptr) { nodeStack.push(current); current = current->next; } // 如果链表为空，则直接返回nullptr if (nodeStack.empty()) return nullptr; // 构建新的链表 ListNode* newHead = nodeStack.top(); // 新链表的头节点为栈顶元素 nodeStack.pop(); ListNode* currentNode = newHead; // 依次从栈中弹出节点并连接成新链表 while (!nodeStack.empty()) { currentNode->next = nodeStack.top(); nodeStack.pop(); currentNode = currentNode->next; } // 设置最后一个节点的next指针为nullptr currentNode->next = nullptr; return newHead; } // 辅助函数：打印链表 void printList(ListNode* head) { ListNode* current = head; while (current != nullptr) { cout << current->val << " "; current = current->next; } cout << endl; } int main() { // 创建测试链表 1 -> 2 -> 3 -> 4 -> 5 ListNode* head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(3); head->next->next->next = new ListNode(4); head->next->next->next->next = new ListNode(5); cout << "Original List: "; printList(head); // 打印原链表 // 调用反转函数 ListNode* reversedHead = reverseListUsingStack(head); cout << "Reversed List: "; printList(reversedHead); // 打印反转后的链表 return 0; } ``` #### 复杂度分析 - **时间复杂度**: O(N)，其中N是链表的长度。需要两次遍历链表，一次将节点压入栈中，另一次从栈中弹出节点重建链表[^4]。 - **空间复杂度**: O(N)，因为额外使用了一个栈来存储所有的链表节点。 --- ###