206. 反转链表 (Swift 版本)
题目
给你单链表的头节点 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 previous: ListNode? = nil// 当前var current: ListNode? = head// 下一个var next: ListNode? = head?.nextwhile next != nil {current?.next = previousprevious = currentcurrent = nextnext = current?.next}// 将新节点的首个节点正确连接current?.next = previousreturn current}
}
分析
- 时间复杂度：因为只遍历了一次，很显然是
O(n)； - 空间复杂度：只用到了 3 个指针，所以是
O(1)；
难点
想写对链表代码，首先就要理解好指针：previous, current. next 是指针类型，存储的是链表节点对象的地址；
谨记：当你执行
current?.next = xxx后（已经将 next 指向新的地址），就无法通过current?.next获取之前的地址了，所以记得提前保存需要的地址；