题目

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

示例 1：

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

示例 2：

• 输入：head = [1,2]
• 输出：[2,1]

示例 3：

• 输入：head = []
• 输出：[]

方法一：迭代

思路及解法

假设链表为 ，我们想要把它改成 。

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

代码

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
    }
}

复杂度分析

• 时间复杂度：，其中 是链表的长度。需要遍历链表一次。

• 空间复杂度：。

方法二：递归

思路及解法

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

假设链表为：

若从节点 到已经被反转，而我们正处于 。

我们希望 的下一个节点指向 。

所以，。

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

代码

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
    }
}

复杂度分析

• 时间复杂度：，其中 是链表的长度。需要对链表的每个节点进行反转操作。

• 空间复杂度：，其中 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 层。