用c++写一个单链表反转的函数
时间: 2024-09-16 10:03:23 浏览: 54
在C++中,可以使用迭代或递归的方式来编写一个单链表反转的函数。这里提供一个简单的迭代方法:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 单链表反转的函数
ListNode* reverseList(ListNode* 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) {
cout << head->val << " -> ";
head = head->next;
}
cout << "nullptr" << endl;
}
int main() {
// 创建一个示例链表
ListNode* list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3);
list->next->next->next = new ListNode(4);
cout << "Original List: ";
printList(list);
// 反转链表
ListNode* reversedList = reverseList(list);
cout << "Reversed List: ";
printList(reversedList);
return 0;
}
```
在这个例子中,`reverseList` 函数接收一个链表的头节点作为输入,通过改变每个节点的 `next` 指针,实现了链表的反转。
阅读全文