一、题目

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

示例 1：

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

示例 2：

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

示例 3：

输入： head = [] 输出：[]

---

二、题解

1. 迭代

1.1. 核心思想

逐个改变节点的 next 指向，让每个节点反过来指向前一个，不能丢失原链表后面部分。

1. pre：记录前一个节点，初始为 nullptr（反转后最后一个节点指向 null）
2. cur：当前正在处理的节点，从头结点开始
3. temp：临时保存 cur 的下一个节点⭐关键

在修改 cur->next 之前，必须先存下原来的后继，不然后面链表直接丢了。

1.2. 代码

/**
 * Definition for singly-linked list.
 * 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* cur = head;
        ListNode* pre = nullptr;
        while(cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

时间复杂度：$O(n)$ 空间复杂度：$O(1)$

2. 递归

2.1. 核心思想

递归的本质：先反转后面的子链表，再处理当前节点 函数定义：reverseList(head)：反转以 head 为头的链表，返回反转后的新头结点。

2.2. 代码

/**
 * Definition for singly-linked list.
 * 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) {
        if(!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

时间复杂度：$O(n)$，每个节点访问一次 空间复杂度：$O(n)$，递归调用栈深度等于链表长度，链表很长会栈溢出。

3. 两种算法对比

对比维度	迭代（双指针）	递归
翻转顺序	从前向后	从后向前
时间复杂度	O(n)	O(n)
空间复杂度	O(1)	O(n)（递归栈）
核心操作	temp 暂存后继，修改 cur->next 指向 pre	先反转子链表，head->next->next=head反向
返回值	pre（新头结点）	newHead（原链表尾）
关键点	必须保存 temp，防止链表断裂	head->next=nullptr，防止成环
优点	原地、无栈溢出，适合长链表	代码简短，逻辑优雅
缺点	指针较多，容易混淆	链表过长会栈溢出
面试推荐	✅优先写	理解思想即可，不优先写

三、206. 反转链表 - 力扣（LeetCode）