题目
给你单链表的头节点 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)
;