设计一个算法,利用一个顺序栈逆置一个带头结点的单链表
时间: 2024-05-11 13:19:53 浏览: 132
第二章第2次单链表答案.ppt
可以使用一个顺序栈来实现单链表的逆置,具体的算法如下:
1. 定义一个顺序栈和一个指向单链表头结点的指针p;
2. 将单链表中的每个节点依次入栈,直到p指向单链表的尾节点;
3. 弹出栈中的元素,并将其以头插法的方式插入到一个新的单链表中;
4. 返回新的单链表的头结点。
代码实现如下:
```c++
Node* reverseList(Node* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
Node* p = head->next; // 指向第一个节点
stack<Node*> s; // 定义顺序栈
while (p != nullptr) {
s.push(p);
p = p->next;
}
Node* newHead = new Node(); // 定义新的头结点
newHead->next = nullptr;
p = newHead;
while (!s.empty()) {
Node* node = s.top();
s.pop();
node->next = nullptr;
p->next = node;
p = p->next;
}
return newHead;
}
```
需要注意的是,由于单链表带头结点,因此逆置操作结束后需要重新定义一个新的头结点。
阅读全文