内容简介：时间复杂度: O(n), 空间复杂度: O(1)这是一道经典的链表题目 - 环形链表，基本的解题思路是双指针技巧里面的快慢指针。这两个指针的适当速度应该是多少？
时间复杂度: O(n), 空间复杂度: O(1)
解题思路
这是一道经典的链表题目 - 环形链表，基本的解题思路是双指针技巧里面的快慢指针。
- 如果没有环，快指针将停在链表的末尾。
- 如果有环，快指针最终将与慢指针相遇。
这两个指针的适当速度应该是多少？
一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
if head == nil || head?.next == nil {
return false
}
var slow = head
var fast = head?.next
while fast?.next != nil && fast?.next?.next != nil {
slow = slow?.next
fast = fast?.next?.next
if slow === fast {
return true
}
}
return false
}
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- Linked List Cycle
- 142. Linked List Cycle II
- LeetCode - 142. Linked List Cycle II
- LeetCode - 141 - 环形链表（linked-list-cycle）
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
大型网站技术架构演进与性能优化
许令波 / 电子工业出版社 / 2018-6 / 79
《大型网站技术架构演进与性能优化》从一名亲历者的角度，阐述了一个网站在业务量飞速发展的过程中所遇到的技术转型等各种问题及解决思路。从技术发展上看，网站经历了Web应用系统从分布式、无线多端、中台到国际化的改造；在解决大流量问题的方向上，涉及了从端的优化到管道到服务端甚至到基础环境优化的各个层面。 《大型网站技术架构演进与性能优化》总结的宝贵经验教训可以帮助读者了解当网站遇到类似问题时，应如何......一起来看看 《大型网站技术架构演进与性能优化》 这本书的介绍吧!
