借助栈(可用栈的基本运算)来实现单链表的逆置运算。
时间: 2023-06-11 13:05:38 浏览: 139
好的,您可以使用下面的 C++ 代码实现:
```
#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;
}
p->next = NULL;
}
return newHead;
}
int main() {
ListNode* head = new ListNode(1); // 构造一个链表1->2->3->4->5
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);
ListNode* newHead = reverseList(head); // 链表逆置
while (newHead != NULL) {
cout << newHead->val << " "; // 输出逆置后的链表
newHead = newHead->next;
}
cout << endl;
return 0;
}
```
以上代码使用栈来实现单链表的逆置运算。时间复杂度为O(n),空间复杂度为O(n),其中n为单链表的长度。
阅读全文