题目描述

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

思考题：

• 请同时实现迭代版本和递归版本。

样例

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

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

算法 1

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

关键点在于用一个指针 pre 记录当前节点的前驱节点

1. 从头节点开始遍历，初始值 pre = nullptr 表示头节点的前驱节点是 NULL
2. 用一个指针 cur 扫描整个链表，将当前节点的 next 域指向它的前驱节点，在此操作之前要先保存 cur 的 next 节点，防止链表丢失。
3. 链表遍历结束，cur 指向 NULL，pre 指向的正是链表的尾节点，同时也是翻转链表的头节点，返回 pre 即可

时间复杂度

遍历链表的时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
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)$

函数 reverseList 的作用就是将链表 head 翻转，那么我们可以拆两步操作

1. 先将 head->next 指向的链表翻转，auto tail = reverseList(head->next) 得到的返回值就是原链表的尾节点，也是翻转后链表的头节点
2. 经翻转后此时 head->next 就是 head->next 所指向链表的尾节点，那么将 head->next 指向头节点 head，再将 head 指向 NULL，就完成了整个链表的翻转

时间复杂度

链表中的每个节点都会被遍历一遍，所以时间复杂度为 $O(n)$，总共需要递归 n 层，系统栈的空间复杂度是 $O(n)$，所以额外空间复杂度为 $O(n)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        auto tail = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }
};