带头结点的单链表逆置
时间: 2023-08-21 22:12:01 浏览: 83
以下是带头结点的单链表逆置的 C++ 代码实现:
```cpp
#include <iostream>
using namespace std;
// 定义链表结点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 定义链表逆置函数
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head->next;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = prev;
return head;
}
// 测试
int main() {
ListNode* head = new ListNode(0);
ListNode* p1 = new ListNode(1);
ListNode* p2 = new ListNode(2);
ListNode* p3 = new ListNode(3);
head->next = p1;
p1->next = p2;
p2->next = p3;
cout << "原链表:";
for (ListNode* p = head->next; p; p = p->next) {
cout << p->val << " ";
}
cout << endl;
head = reverseList(head);
cout << "逆置后链表:";
for (ListNode* p = head->next; p; p = p->next) {
cout << p->val << " ";
}
cout << endl;
return 0;
}
```
该代码中,reverseList 函数实现了链表的逆置操作,head 为带头结点的链表头。在逆置过程中,需要用到三个指针 prev、curr 和 next,分别表示前驱结点、当前结点和后继结点。具体实现方式是,每次将 curr 结点的 next 指针指向 prev,然后将 prev、curr 和 next 分别后移一个结点,直到 curr 结点为空。最后将头结点的 next 指针指向逆置后的链表头结点 prev。
阅读全文