就像 A 和 B 两个人跑步,A 跑步速度是 B 跑步速度的两倍。两人同时从同一起点开始跑。排除跑道长度为 0 的情况: 1. A 跑到了跑道的尽头,此时 B 在跑道的中间,那么这个跑道肯定不是一个环形跑道。 2. A 和 B 相遇。在 A、B 速度不同的情况下,如果除起点外还可以再次相遇,那么这个跑道,不管是圆形还是6字型,肯定是环形跑道。
代码
1
/**
2
* @param {ListNode} head
3
* @return {boolean}
4
*/
5
6
consthasCycle=function(head){
7
if(!head)returnfalse;
8
let fast = head;
9
let slow = head;
10
while(fast && fast.next){
11
fast = fast.next.next;
12
slow = slow.next;
13
if(fast === slow)returntrue;
14
}
15
returnfalse;
16
};
Copied!
复杂度分析
时间复杂度:
O(n)
对于含有 n 个元素的单向链表,指针移动到尾部的时间为
O(n)
; 对于含有 n 个元素的环形链表,指针移动的时间为 第一次指针移动到尾部的时间 + 指针再次移动到两指针相遇的节点的时间 =
和哈希表不一样的是,哈希表是将遍历过节点存到一个 Map 对象中,若循环到一个节点,且对象中存在该节点,则证明为环形链表。而这个方法是将当前节点的 val 值改为用 Symbol 创建的一个独一无二的值,若链表循环过程中存在节点的 val 全等于这个值,那么证明当前不是第一次循环到该节点,即链表为环形链表,反之不是。