1.题目介绍

2.题解

2.1 迭代

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

作者：力扣官方题解
链接：https://leetcode.cn/problems/reverse-linked-list/solutions/551596/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

//
// Created by trmbh on 2023-10-28.
//
#include <iostream>
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) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *dummy = new ListNode(0); //使用虚拟头结点 辅助存储下一节点
        ListNode *pre = nullptr; //存储前一节点
        ListNode *curr = head; //存储当前节点
        while (curr){
            dummy -> next = curr -> next; //记住下一个节点
            curr -> next = pre;  //修改当前节点指向方向
            pre = curr; //当前节点变为下次循环的前一个节点
            curr = dummy -> next; // 更改当前节点位置
        }
        return pre; // 此时当前节点已经指向nullptr，前一节点pre即为所需
    }
};

int main(){
    ListNode l1(5);
    ListNode l2(4, &l1);
    ListNode l3(3, &l2);
    ListNode l4(2, &l3);
    ListNode head(1, &l4);
    Solution solution;
    ListNode *h = solution.reverseList(&head);
    auto p = h;
    while (p){
        std::cout << p->val << ' ' ;
        p = p->next;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
空间复杂度：O(1)。

2.2 递归

递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？
$\text{假设链表为:}\quad n_1\rightarrow\ldots\rightarrow n_{k-1}\rightarrow n_k\rightarrow n_{k+1}\rightarrow\ldots\rightarrow n_m\rightarrow\varnothing $

$\text{若从节点 }n_{k+1}\text{ 到 }n_m\text{ 已经被反转,而我们正处于 }n_k\text{。}$
$n_1\rightarrow\ldots\rightarrow n_{k-1}\rightarrow n_k\rightarrow n_{k+1}\leftarrow\ldots\leftarrow n_m$

$\text{我们希望 }n_{k+1}\text{ 的下一个节点指向 }n_k.$
$\text{所以,}n_k.next.next=n_k\text{。}$

需要注意的是 $n_1$ 的下一个节点必须指向 $\varnothing$。如果忽略了这一点，链表中可能会产生环。