LeetCode 算法：反转链表 c++

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

题目

给你单链表的头节点 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

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

题解

迭代法

1. 题解：

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

• 迭代方法
  • 初始化三个指针：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：防止链表形成环。
  • 返回新的头节点：递归调用返回的头节点。

2. 复杂度：时间复杂度O(n)，空间复杂度O(1)。
3. 过程：迭代法如下代码。
4. 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;
}

• 输出结果：

Original List: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr
Reversed List: 5 -> 4 -> 3 -> 2 -> 1 -> nullptr