将链表反转的问题
1.设计一个函数，传入链表的头指针，实现将链表反转。示例：
链表节点定义：
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
函数接口定义：
ListNode* reverseList(ListNode* head) {
//完成该函数
}
在这个问题中，我们需要实现一个函数 reverseList，它接收一个链表的头指针，然后将链表反转。我们可以通过迭代或递归的方式来实现这个功能。这里，我将展示一种迭代的实现方法：
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr; // 初始化前一个节点指针
ListNode* current = head; // 初始化当前节点指针
ListNode* nextNode = nullptr; // 初始化下一个节点指针
while (current != nullptr) {
nextNode = current->next; // 保存当前节点的下一个节点
current->next = prev; // 将当前节点的下一个节点指向前一个节点，完成反转
prev = current; // 更新前一个节点为当前节点
current = nextNode; // 更新当前节点为下一个节点
}
return prev; // 返回反转后链表的头节点
}
int main() {
// 构造一个简单的链表：1 -> 2 -> 3 -> nullptr
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
// 反转链表并打印
ListNode* reversedHead = reverseList(head);
while (reversedHead != nullptr) {
std::cout << reversedHead->val << " -> ";
reversedHead = reversedHead->next;
}
std::cout << "nullptr" << std::endl;
return 0;
}
这个代码中，reverseList 函数首先初始化了 prev、current 和 nextNode 三个指针。然后通过一个 while 循环遍历链表中的每个节点，
将当前节点的 next 指针指向前一个节点以实现反转。在循环中，我们会更新 prev 和 current 指针以便处理下一个节点。
最后，当 current 指针指向 nullptr 时，循环结束，返回 prev 指针，即反转后链表的头节点。
页:
[1]