题目

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]

输出：[2,1]

示例 3：

输入：head = []

输出：[]

方法一：迭代

思路及解法

假设链表为 $1 \rightarrow 2 \rightarrow 3 \rightarrow \varnothing$ ，我们想要把它改成 $\varnothing \leftarrow 1 \leftarrow 2 \leftarrow 3$ 。

在遍历链表时，将当前节点的 $\textit{next}$ 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

代码

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var prev: ListNode? = nil
        var curr: ListNode? = head
        while nil != curr {
            let next: ListNode? = curr?.next
            curr?.next = prev
            prev = curr
            curr = next
        }
        return prev
    }
}

复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 是链表的长度。需要遍历链表一次。
空间复杂度： $O(1)$ 。

方法二：递归

思路及解法

递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？

假设链表为：

$n_1→…→n_{k−1}→n_k→n_{k+1}→…→n_m→\varnothing$

若从节点 $n_{k+1}$ 到 $n_m$ 已经被反转，而我们正处于 $n_k$ 。

$n_1→…→n_{k−1}→n_k→n_{k+1}←…←n_m$

我们希望 $n_{k+1}$ 的下一个节点指向 $n_k$ 。

所以， $n_k.\textit{next}.\textit{next} = n_k$ 。

需要注意的是 $n_1$ 的下一个节点必须指向 $\varnothing$ 。如果忽略了这一点，链表中可能会产生环。

代码

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if nil == head || nil == head?.next {
            return head
        }
        var newHead: ListNode? = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        return newHead
    }
}