用c++语言编写一个reverse函数使得链表能够实现翻转
时间: 2024-10-08 09:24:47 浏览: 20
在C++中,我们可以创建一个`ListNode`结构体表示链表节点,并实现一个`reverseList`函数来翻转链表。这里是一个简单的例子:
```cpp
#include <iostream>
// 链表节点定义
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 翻转链表的辅助函数
ListNode* reverseHelper(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; // 返回新的头节点
}
// 主函数示例
ListNode* reverseList(ListNode* head) {
return reverseHelper(head);
}
// 打印链表
void printList(ListNode* head) {
ListNode* node = head;
while (node != nullptr) {
std::cout << node->val << " -> ";
node = node->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);
delete list; // 释放内存
return 0;
}
```
这个程序首先定义了一个链表结构,然后实现了一个递归辅助函数`reverseHelper`来完成实际的链表翻转操作。最后,在`main`函数中创建了一个链表并打印了原链表和翻转后的链表。