用c++98写一算法,借助于栈将一个存放202300705055的单链表逆序输出。
时间: 2024-10-20 10:05:00 浏览: 32
在 C++98 中,我们可以使用栈的数据结构配合迭代器来实现单链表的逆序操作。这里是一个简单的示例代码:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
void reverseList(ListNode* &head) {
if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个元素,无需反转
return;
}
// 创建辅助栈
stack<ListNode*> s;
ListNode* curr = head; // 当前节点指针
while (curr != NULL) {
s.push(curr); // 将当前节点压入栈
curr = curr->next; // 移动到下一个节点
}
// 从栈顶开始弹出并连接节点,形成新的逆序链表
curr = head;
while (!s.empty()) {
ListNode* temp = s.top();
s.pop(); // 弹出栈顶节点
temp->next = curr; // 连接
curr = temp; // 更新当前节点为刚连接的节点
}
curr->next = NULL; // 确保最后一个节点之后没有额外的链接
}
int main() {
// 假设头节点已经初始化,例如:
ListNode* head = new ListNode(202300705055);
// ...(链表的其他节点添加)
reverseList(head);
// 打印逆序后的链表
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
return 0;
}
```
这段代码首先检查链表是否为空,然后遍历原链表并将每个节点压入栈中。接着,它从栈顶开始取出节点,并将其插入到原链表的适当位置,形成逆序链表。
阅读全文