0206. 反转链表

0206. 反转链表 #

标签：链表
难度：简单

题目大意 #

描述：给定一个单链表的头节点 head。

要求：将该单链表进行反转。可以迭代或递归地反转链表。

说明：

链表中节点的数目范围是 $[0, 5000]$。
$-5000 \le Node.val \le 5000$。

示例：

示例 1：

1
2
3
4
5


输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
解释：
翻转前    1->2->3->4->5->NULL
反转后    5->4->3->2->1->NULL

解题思路 #

思路 1：迭代 #

使用两个指针 cur 和 pre 进行迭代。pre 指向 cur 前一个节点位置。初始时，pre 指向 None，cur 指向 head。
将 pre 和 cur 的前后指针进行交换，指针更替顺序为：
1. 使用 next 指针保存当前节点 cur 的后一个节点，即 next = cur.next；
2. 断开当前节点 cur 的后一节点链接，将 cur 的 next 指针指向前一节点 pre，即 cur.next = pre；
3. pre 向前移动一步，移动到 cur 位置，即 pre = cur；
4. cur 向前移动一步，移动到之前 next 指针保存的位置，即 cur = next。
继续执行第 2 步中的 1、2、3、4。
最后等到 cur 遍历到链表末尾，即 cur == None，时，pre 所在位置就是反转后链表的头节点，返回新的头节点 pre。

使用迭代法反转链表的示意图如下所示：

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur != None:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

思路 1：复杂度分析 #

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

思路 2：递归 #

具体做法如下：

首先定义递归函数含义为：将链表反转，并返回反转后的头节点。
然后从 head.next 的位置开始调用递归函数，即将 head.next 为头节点的链表进行反转，并返回该链表的头节点。
递归到链表的最后一个节点，将其作为最终的头节点，即为 new_head。
在每次递归函数返回的过程中，改变 head 和 head.next 的指向关系。也就是将 head.next 的next 指针先指向当前节点 head，即 head.next.next = head 。
然后让当前节点 head 的 next 指针指向 None，从而实现从链表尾部开始的局部反转。
当递归从末尾开始顺着递归栈的退出，从而将整个链表进行反转。
最后返回反转后的链表头节点 new_head。

使用递归法反转链表的示意图如下所示：

思路 2：代码 #

1
2
3
4
5
6
7
8


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

思路 2：复杂度分析 #

时间复杂度：$O(n)$
空间复杂度：$O(n)$。最多需要 $n$ 层栈空间。

参考资料 #

【题解】反转链表 - 反转链表 - 力扣
【题解】【反转链表】：双指针，递归，妖魔化的双指针 - 反转链表 - 力扣（LeetCode）