C++实现单链表的就地逆置
时间: 2024-09-11 21:02:52 浏览: 19
在C++中,单链表的就地逆置(也称原地逆序或反转)是指不额外分配空间,直接修改原有链表节点的指针,使得整个链表的顺序反转。以下是通过迭代方法实现的一种简单方法:
```cpp
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
void reverseList(ListNode* &head) {
if (head == nullptr || head->next == nullptr) {
return; // 如果链表为空或者只有一个节点,无需反转
}
ListNode *prev = nullptr, *curr = head, *nextTemp = nullptr;
// 遍历链表,每次把当前节点的下一个节点保存到临时变量,然后更新当前节点的next指向其前一个节点
while (curr != nullptr) {
nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
// 最后,原来的头节点变成新的尾节点
head = prev;
}
// 测试
int main() {
ListNode *head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
std::cout << "Original list: ";
printList(head); // 输出原始链表
reverseList(head);
std::cout << "Reversed list: ";
printList(head); // 输出反转后的链表
return 0;
}
// 辅助函数:打印链表
void printList(ListNode* node) {
while (node != nullptr) {
std::cout << node->val << " -> ";
node = node->next;
}
std::cout << "nullptr" << std::endl;
}
```