LeetCode 算法：反转链表 c++

embedded/2024/10/18 5:41:08/

原题链接🔗：反转链表
难度：简单⭐️

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

在这里插入图片描述

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
在这里插入图片描述

输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

题解

迭代法

题解：

有两种常见的方法来解决这个问题：迭代和递归。

迭代方法
初始化三个指针：prev 初始化为 nullptr（因为反转后的链表第一个节点的 next 应该是nullptr），current 初始化为头节点 head，next 用于临时存储下一个节点。
遍历链表：使用一个循环，当 current 不为 nullptr 时，执行以下操作：
保存 current 的下一个节点到 next。
将 current 的 next 指向 prev，实现反转。
更新 prev 和 current 为下一个节点：prev = current，current = next。

当循环结束时，prev 将指向反转后的头节点，返回 prev。

递归方法
基本情况：如果 head 是 nullptr 或者 head->next 是 nullptr，说明链表为空或只有一个节点，直接返回 head。
递归反转：递归调用 reverseList 函数，传入 head->next 作为参数，获取反转后的链表的头节点。
重新链接节点：将当前节点 head 的下一个节点的 next 指向 head，实现反转。
设置当前节点的 next 为 nullptr：防止链表形成环。
返回新的头节点：递归调用返回的头节点。

复杂度：时间复杂度O(n)，空间复杂度O(1)。
过程：迭代法如下代码。
c++ demo：

#include <iostream>// 定义链表节点
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 解决方案类
class Solution {
public:// 迭代方法反转链表ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* current = head;ListNode* next = nullptr;while (current != nullptr) {next = current->next; // 保存下一个节点current->next = prev; // 反转当前节点的指针prev = current;       // 移动prev到当前节点current = next;       // 移动current到下一个节点}return prev; // 返回新的头节点}
};// 主函数，用于演示
int main() {Solution solution;// 创建一个示例链表: 1 -> 2 -> 3 -> 4 -> 5ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);head->next->next->next->next = new ListNode(5);// 打印原始链表std::cout << "Original List: ";ListNode* current = head;while (current != nullptr) {std::cout << current->val << " -> ";current = current->next;}std::cout << "nullptr" << std::endl;// 反转链表ListNode* reversedHead = solution.reverseList(head);// 打印反转后的链表std::cout << "Reversed List: ";current = reversedHead;while (current != nullptr) {std::cout << current->val << " -> ";current = current->next;}std::cout << "nullptr" << std::endl;// 释放链表内存while (reversedHead != nullptr) {ListNode* tmp = reversedHead;reversedHead = reversedHead->next;delete tmp;}return 0;
}