给出代码,写算法,借助于栈将一个单链表逆置。
时间: 2023-06-14 18:04:15 浏览: 111
算法步骤如下:
1. 定义一个栈和一个指向单链表头节点的指针。
2. 将单链表中的每个节点依次压入栈中。
3. 弹出栈顶节点,将其作为新的节点插入到单链表的表头。
4. 重复步骤3,直到栈为空,即所有节点都已被插入到单链表的表头。
以下是用 C++ 实现的代码:
```cpp
#include <iostream>
#include <stack>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
stack<ListNode*> s;
ListNode* p = head;
while (p != NULL) {
s.push(p);
p = p->next;
}
ListNode* newHead = NULL;
if (!s.empty()) {
newHead = s.top();
s.pop();
p = newHead;
}
while (!s.empty()) {
p->next = s.top();
s.pop();
p = p->next;
}
if (p != NULL) {
p->next = NULL;
}
return newHead;
}
int main() {
ListNode* n1 = new ListNode(1);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(3);
ListNode* n4 = new ListNode(4);
ListNode* n5 = new ListNode(5);
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
ListNode* newHead = reverseList(n1);
while (newHead != NULL) {
cout << newHead->val << " ";
newHead = newHead->next;
}
cout << endl;
return 0;
}
```
输出结果为:`5 4 3 2 1`
阅读全文
相关推荐









