反转链表 | 秋招知识库

方法一：递归（尾插法）

递归递归，有递有归。

我们先「递」到链表的末尾节点，作为新链表的头节点。然后在「归」的过程中，一个一个地把节点插在新链表的末尾。

新链表的末尾节点在哪？就是当前节点的 $next$ 。具体实现如下。

Python 解法1C++ 解法1

python

class Solution:
    # 首先「递」到链表末尾，把末尾节点作为新链表的头节点 rev_head
    # 然后在「归」的过程中，把经过的节点依次插在新链表的末尾（尾插法）
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 判断 head is None 是为了兼容一开始链表就是空的情况
        if head is None or head.next is None:
            return head  # 链表末尾，即下面的 rev_head
        rev_head = self.reverseList(head.next)  # 「递」到链表末尾，拿到新链表的头节点
        tail = head.next  # 在「归」的过程中，head.next 就是新链表的末尾
        tail.next = head  # 把 head 插在新链表的末尾
        head.next = None  # 如果不写这行，新链表的末尾两个节点成环，这俩节点互相指向对方
        return rev_head

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    // 首先「递」到链表末尾，把末尾节点作为新链表的头节点 rev_head
    // 然后在「归」的过程中，把经过的节点依次插在新链表的末尾（尾插法）
    ListNode* reverseList(ListNode* head) {
        // 判断 head == nullptr 是为了兼容一开始链表就是空的情况
        if (head == nullptr || head->next == nullptr) {
            return head; // 链表末尾，即下面的 rev_head
        }
        auto rev_head = reverseList(head->next); // 「递」到链表末尾，拿到新链表的头节点
        ListNode* tail = head->next; // 在「归」的过程中，head->next 就是新链表的末尾
        tail->next = head; // 把 head 插在新链表的末尾
        head->next = nullptr; // 如果不写这行，新链表的末尾两个节点成环，这俩节点互相指向对方
        return rev_head;
    }
};

答疑

问：为什么不写 head.next = null 的代码，会提示「超出内存限制」？这应该是超时呀？

答：这和力扣的判题机制有关，评测机会先把链表转成字符串，再去比对答案。这会遍历链表，如果链表有环，生成的字符串会无限延长，在超时之前就超出内存限制了。

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为链表节点个数。
空间复杂度： $O (n)$ 。递归需要 $O (n)$ 的栈空间。

方法二：迭代（头插法）

视频讲解：【基础算法精讲 06】，制作不易，欢迎点赞~

简单理解：比如链表为 $1 \to 2 \to 3$ 。创建一个新的空链表，然后用头插法依次把节点 $1, 2, 3$ 插到这个新链表的头部，就得到了链表 $3 \to 2 \to 1$ ，这正是反转后的链表。

头插法的意思是，把一个节点 $node$ 指向链表头节点（ $node . next$ 更新为链表头节点），那么 $node$ 就插在了链表的左侧，新链表的头节点为 $node$ 。

对于链表 $1 \to 2 \to 3$ ，结合代码来说，顺序为：

第一轮循环结束后，得到链表 $1$ 。
第二轮循环结束后，得到链表 $2 \to 1$ 。
第三轮循环结束后，得到链表 $3 \to 2 \to 1$ 。

注：代码每轮循环结束后， $pre$ 表示最新得到的链表。

Python 解法3C++ 解法3

python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre  # 把 cur 插在 pre 链表的前面（头插法）
            pre = cur
            cur = nxt
        return pre

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = pre; // 把 cur 插在 pre 链表的前面（头插法）
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为链表节点个数。
空间复杂度： $O (1)$ 。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一：递归（尾插法） ​

答疑 ​

复杂度分析 ​

方法二：迭代（头插法） ​

复杂度分析 ​

分类题单 ​

方法一：递归（尾插法）

答疑

复杂度分析

方法二：迭代（头插法）

复杂度分析

分类题单