先定义一个单向链表
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
迭代法
依次遍历每个结点，将该结点 next 指向上一个结点，用一个临时变量保存上一个结点
- 时间复杂度：O(n)，因为涉及到遍历
- 空间复杂度：O(1)，没有额外开销
class Solution { func reverseList(_ head: ListNode?) -> ListNode? { // 上一个结点 var pre: ListNode? // 当前结点 var cur = head while cur != nil { // 当前结点的下一个结点 let next = cur!.next // 将当前结点的next指向上一个结点 cur!.next = pre // 向后移动上一个结点和当前结点 pre = cur cur = next } return pre } }
递归法
- 时间复杂度：O(n)，因为涉及到遍历
- 空间复杂度：O(n)，因为递归的深度会有额外开销
class Solution { func reverseList(_ head: ListNode?) -> ListNode? { // 终止条件 if head == nil || head?.next == nil { return head } let node = reverseList(head?.next) // 反转当前结点和下一结点 head?.next?.next = head // 当前结点指向nil head?.next = nil return node } }
