题目描述

[EN | CN]

反转一个单链表。

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

解法 1:迭代

举个例子,例如在反转的过程中,我们有链表如下: $$ \begin{aligned} &\text{A (newhead)} \rightarrow \text{B} \rightarrow \cdots \rightarrow \text{C} \\ &\boxed{\text{D}}\text{ (head)} \rightarrow \text{E} \rightarrow \text{F} \rightarrow \cdots \end{aligned} $$

其中以 $\text{newhead}$ 开始的链表是已反转的,以 $\text{head}$ 开始的链表是未反转的开头,那么我们在这一步的目标就是获得: $$ \begin{aligned} &\boxed{\text{D}}\text{ (newhead)} \rightarrow \text{A} \rightarrow \text{B} \rightarrow \cdots \rightarrow \text{C} \\ &\text{E (head)} \rightarrow \text{F} \rightarrow \cdots \end{aligned} $$

如图,我们将结点 $\text{D}$ 插入到了已反转链表中,并且更新了 $\text{newhead}$ 与 $\text{head}$ 指针,依次类推。

每一步的具体实现步骤不具体展开了,大致就是用临时指针挂住 $\text{head.next}$,然后 $\text{head}$ 指向的结点插入到 $\text{newhead}$ 这边,更新 $\text{newhead}$、$\text{head}$ 指针。

假设 $n$ 为链表长度,那么

  • 时间复杂度为 $O(n)$,需要遍历一次;
  • 空间复杂度为 $O(1)$,如果可以操作原链表就不需要额外空间,否则需要 $O(n)$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = None
        while head:
            head.next, new_head, head = new_head, head, head.next
        return new_head
  • 执行用时:40 ms,在所有 Python3 提交中击败了 75.64% 的用户。
  • 内存消耗:14.5 MB,在所有 Python3 提交中击败了 25.00% 的用户。

解法 2:递归

回顾一下递归三部曲:

  1. 分解问题为更小规模的问题 。每反转一个链表,都相当于反转从它的第二个结点开始的链表 reversed,再在结尾拼上当前头结点 head
  2. 递归关系式。如上,不过要注意两处指针:
    1. 反转之后,head.next 实际上指向了 reserved 的最后一个结点,所以直接让这一结点的 next 指向 head 即可。
    2. 头结点 head 的 next 指针记得改为 None。
  3. 终止条件。如果当前链表长度为 1,则直接返回。

假设 $n$ 为链表长度,那么

  • 时间复杂度为 $O(n)$,至少需要一次遍历;
  • 空间复杂度为 $O(n)$,因为需要建立一个深度为 $n$ 的栈来进行递归,所以需要 $O(n)$ 空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        reversed = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return reversed
  • 执行用时:48 ms,在所有 Python3 提交中击败了 40.23% 的用户。
  • 内存消耗:18.6 MB,在所有 Python3 提交中击败了 5.04% 的用户。