题目

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

解题

swift">/**
 * 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 previous: ListNode? = nil
        // 当前
        var current: ListNode? = head
        // 下一个
        var next: ListNode? = head?.next
        while next != nil {
            current?.next = previous
            previous = current
            current = next
            next = current?.next
        }
        // 将新节点的首个节点正确连接
        current?.next = previous
        return current
    }
}

分析

• 时间复杂度：因为只遍历了一次，很显然是 O(n)；
• 空间复杂度：只用到了 3 个指针，所以是 O(1)；