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 

// 定义链表节点
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 -> 5
    ListNode* 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