[已解决]将链表反转的问题

白痴爱面包

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) {
//完成该函数
}

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-2 21:19:19

在这个问题中，我们需要实现一个函数 reverseList，它接收一个链表的头指针，然后将链表反转。我们可以通过迭代或递归的方式来实现这个功能。这里，我将展示一种迭代的实现方法：

1. #include <iostream>
   
2. 
   
3. struct ListNode {
   
4.     int val;
   
5.     ListNode *next;
   
6.     ListNode() : val(0), next(nullptr) {}
   
7.     ListNode(int x) : val(x), next(nullptr) {}
   
8.     ListNode(int x, ListNode *next) : val(x), next(next) {}
   
9. };
   
10. 
    
11. ListNode* reverseList(ListNode* head) {
    
12.     ListNode* prev = nullptr; // 初始化前一个节点指针
    
13.     ListNode* current = head; // 初始化当前节点指针
    
14.     ListNode* nextNode = nullptr; // 初始化下一个节点指针
    
15. 
    
16.     while (current != nullptr) {
    
17.         nextNode = current->next; // 保存当前节点的下一个节点
    
18.         current->next = prev; // 将当前节点的下一个节点指向前一个节点，完成反转
    
19.         prev = current; // 更新前一个节点为当前节点
    
20.         current = nextNode; // 更新当前节点为下一个节点
    
21.     }
    
22. 
    
23.     return prev; // 返回反转后链表的头节点
    
24. }
    
25. 
    
26. int main() {
    
27.     // 构造一个简单的链表：1 -> 2 -> 3 -> nullptr
    
28.     ListNode* head = new ListNode(1);
    
29.     head->next = new ListNode(2);
    
30.     head->next->next = new ListNode(3);
    
31. 
    
32.     // 反转链表并打印
    
33.     ListNode* reversedHead = reverseList(head);
    
34.     while (reversedHead != nullptr) {
    
35.         std::cout << reversedHead->val << " -> ";
    
36.         reversedHead = reversedHead->next;
    
37.     }
    
38.     std::cout << "nullptr" << std::endl;
    
39. 
    
40.     return 0;
    
41. }
    

复制代码

这个代码中，reverseList 函数首先初始化了 prev、current 和 nextNode 三个指针。然后通过一个 while 循环遍历链表中的每个节点，

将当前节点的 next 指针指向前一个节点以实现反转。在循环中，我们会更新 prev 和 current 指针以便处理下一个节点。

最后，当 current 指针指向 nullptr 时，循环结束，返回 prev 指针，即反转后链表的头节点。

跳转到最佳答案楼层

isdkz

在这个问题中，我们需要实现一个函数 reverseList，它接收一个链表的头指针，然后将链表反转。我们可以通过迭代或递归的方式来实现这个功能。这里，我将展示一种迭代的实现方法：

1. #include <iostream>
   
2. 
   
3. struct ListNode {
   
4.     int val;
   
5.     ListNode *next;
   
6.     ListNode() : val(0), next(nullptr) {}
   
7.     ListNode(int x) : val(x), next(nullptr) {}
   
8.     ListNode(int x, ListNode *next) : val(x), next(next) {}
   
9. };
   
10. 
    
11. ListNode* reverseList(ListNode* head) {
    
12.     ListNode* prev = nullptr; // 初始化前一个节点指针
    
13.     ListNode* current = head; // 初始化当前节点指针
    
14.     ListNode* nextNode = nullptr; // 初始化下一个节点指针
    
15. 
    
16.     while (current != nullptr) {
    
17.         nextNode = current->next; // 保存当前节点的下一个节点
    
18.         current->next = prev; // 将当前节点的下一个节点指向前一个节点，完成反转
    
19.         prev = current; // 更新前一个节点为当前节点
    
20.         current = nextNode; // 更新当前节点为下一个节点
    
21.     }
    
22. 
    
23.     return prev; // 返回反转后链表的头节点
    
24. }
    
25. 
    
26. int main() {
    
27.     // 构造一个简单的链表：1 -> 2 -> 3 -> nullptr
    
28.     ListNode* head = new ListNode(1);
    
29.     head->next = new ListNode(2);
    
30.     head->next->next = new ListNode(3);
    
31. 
    
32.     // 反转链表并打印
    
33.     ListNode* reversedHead = reverseList(head);
    
34.     while (reversedHead != nullptr) {
    
35.         std::cout << reversedHead->val << " -> ";
    
36.         reversedHead = reversedHead->next;
    
37.     }
    
38.     std::cout << "nullptr" << std::endl;
    
39. 
    
40.     return 0;
    
41. }
    

复制代码

这个代码中，reverseList 函数首先初始化了 prev、current 和 nextNode 三个指针。然后通过一个 while 循环遍历链表中的每个节点，

将当前节点的 next 指针指向前一个节点以实现反转。在循环中，我们会更新 prev 和 current 指针以便处理下一个节点。

最后，当 current 指针指向 nullptr 时，循环结束，返回 prev 指针，即反转后链表的头节点。