原地反转链表代码,C或C++
时间: 2024-10-14 08:15:35 浏览: 20
原地反转链表是指不创建新的节点,直接通过修改现有节点的指针来改变链表的顺序。这里是一个简单的C++实现,使用迭代方法:
```cpp
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head; // 如果链表为空或只有一个元素,直接返回
}
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* temp = curr->next; // 记录当前节点的下一个节点
curr->next = prev; // 将当前节点的next指向前一个节点
prev = curr; // 更新前一个节点为当前节点
curr = temp; // 移动到下一个节点
}
return prev; // 返回新头节点
}
// 测试函数
void printList(ListNode* head) {
while (head != nullptr) {
std::cout << head->val << " -> ";
head = head->next;
}
std::cout << "nullptr" << std::endl;
}
int main() {
ListNode* list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3);
std::cout << "Original List: ";
printList(list);
list = reverseList(list);
std::cout << "Reversed List: ";
printList(list);
return 0;
}
```
这段代码首先检查链表是否为空或只有一个元素,然后通过三个指针prev、curr和temp来交换节点的前后位置。最后返回新的头节点,实现了链表的反转。
阅读全文