206. 反转链表
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
示例一：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例二：
输入：head = [1,2]
输出：[2,1]
示例三：
输入：head = []
输出：[]
解题方法一：迭代
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var curr = head
while curr != nil {
let next = curr!.next
curr!.next = prev
prev = curr
curr = next
}
return prev
}
}
解题思路
假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点 prev。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
复杂度分析
- 时间复杂度：
O(n)，其中n是链表的长度。需要遍历链表一次。 - 空间复杂度：
O(1)。
解题方法二：递归
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head!.next == nil {
return head
}
let newHead = reverseList(head!.next)
head!.next!.next = head
head!.next = nil
return newHead
}
}
解题思路
递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？
假设链表为：
n(1)→..→n(k-1)→n(k)→n(k+1)→...→n(m)→∅
若从节点 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).next.next = n(k)。
需要注意的是 n(1) 的下一个节点必须指向 ∅。如果忽略了这一点，链表中可能会产生环。
复杂度分析
- 时间复杂度：
O(n)，其中n是链表的长度。需要对链表的每个节点进行反转操作。 - 空间复杂度：
O(n)，其中n是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为n层。