题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

$0 <= 节点个数 <= 5000$

注意 ：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

---

算法 1

(链表,迭代) $O(n)$

创建一个前驱节点 $pre$，初始值为 $nullptr$，使用一个指针 $cur$ 遍历链表

$cur$ 不为空执行以下操作：

1. 首先需要把当前节点的下一个节点存起来，防止链表断裂
2. 让当前节点的 $next$ 指向前驱节点
3. 当前节点指向下一个节点，前驱节点指向当前节点
4. 循环以上步骤直到当前节点为 $nullptr$

最终 $pre$ 存的就是翻转后链表的头节点

时间复杂度

只需遍历一遍链表，所以时间复杂度为 $O(n)$，$n$ 为链表的长度

空间复杂度

$O(1)$

代码

/**
 * 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* pre = nullptr;
        auto cur = head;
        while (cur) {
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

算法 2

(链表,递归) $O(n)$

递归的步骤

0. 递归出口条件：如果链表为空或链表只有一个节点，则不需要翻转，直接返回头节点即可。
1. 翻转头节点为 $head->next$ 的链表，得到尾节点 $tail$，即翻转后链表的头节点（因为以 $head->next$ 为头节点的链表和以 $head$ 为头节点的链表的尾节点是一样的）。
2. 然后将 $head->next$ 链表的头节点的 $next$ 指向原链表的头节点，head->next->next = head。
3. 最后将原链表的 $next$ 指向空

最终返回翻转后链表的头节点即 $tail$

时间复杂度

链表中的每个节点只被遍历一遍，所以时间复杂度为 $O(n)$，$n$ 为链表的长度

空间复杂度

递归的深度为 $n$，系统栈的空间复杂度为 $O(n)$，所以额外空间复杂度为 $O(n)$

代码

/**
 * 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;
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};