Linked List Cycle
- leetcode: Linked List Cycle | LeetCode OJ
- lintcode:
- 慢指针初始化为, 快指针初始化为
head
的下一个节点,这是快慢指针初始化的一种方法,有时会简化边界处理,但有时会增加麻烦,比如该题的进阶版。
- 在无环时,快指针每次走两步走到尾部节点,遍历的时间复杂度为 $$O(n/2)$$.
- 有环时,最坏的时间复杂度近似为 $$O(n)$$. 最坏情况下链表的头尾相接,此时快指针恰好在慢指针前一个节点,还需 n 次快慢指针相遇。最好情况和无环相同,尾节点出现环。