- 操作系统：ubuntu22.04
- IDE:Visual Studio Code
- 编程语言：C++11
题目描述
输入一个链表，输出该链表反转之后的链表。例如：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
解决方案
这个问题可以通过多种方法解决，包括递归法和迭代法。下面分别介绍这两种方法。
方法一：迭代法
使用三个指针来逐步反转链表中的每一个节点，直到遍历完整个链表。
代码实现（C++）
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* nextTemp = curr->next; // 暂存当前节点的下一个节点curr->next = prev; // 将当前节点指向前驱节点prev = curr; // 移动前驱节点到当前节点curr = nextTemp; // 移动到下一个待处理节点}return prev; // 新的头节点是原链表的最后一个节点
}int main()
{ListNode* node1 = new ListNode(1);node1->next = new ListNode(2);node1->next->next = new ListNode(3);node1->next->next->next = new ListNode(4);node1->next->next->next->next = new ListNode(5);ListNode* res = reverseList(node1);ListNode *head = res;while(res != nullptr){std::cout<< res->val<<std::endl;res = res->next;}
}
输出：
5
4
3
2
1
方法二：递归法
递归地反转链表，对于每个节点，假设其后续节点已经被正确反转，然后调整当前节点的指向。
代码实现（C++）
struct ListNode {int val;ListNode* next;ListNode( int x ) : val( x ), next( nullptr ) {}
};
ListNode* reverseList( ListNode* head )
{// 基本情况：如果头节点为空或只有一个节点，则直接返回头节点if ( head == nullptr || head->next == nullptr ){return head;}// 递归调用，反转剩余链表ListNode* p = reverseList( head->next );// 反转当前节点与下一个节点之间的连接head->next->next = head;head->next = nullptr;return p; // 返回新的头节点
}int main()
{ListNode* node1 = new ListNode(1);node1->next = new ListNode(2);node1->next->next = new ListNode(3);node1->next->next->next = new ListNode(4);node1->next->next->next->next = new ListNode(5);ListNode* res = reverseList(node1);ListNode *head = res;while(res != nullptr){std::cout<< res->val<<std::endl;res = res->next;}
}
输出：
5
4
3
2
1
