- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
链表的基础知识可以移步这个题解，这里不再赘述。
快慢指针
1.使用快慢不同的两个指针遍历，快指针一次走两步，慢指针一次走一步。
2.如果没有环，快指针会先到达尾部，返回 false。
3.如果有环，则一定会相遇。
consthasCycle=function(head){if(!head||!head.next)returnfalse;letfast=head.next;letslow=head;while(fast!==slow){if(!fast||!fast.next){returnfalse;}fast=fast.next.next;slow=slow.next;}returntrue;};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
标记法
遍历链表，通过 flag 标记判断是否有环，如果标记存在则有环。(走过的地方插个旗子做标记)
consthasCycle=function(head){while(head){if(head.flag){returntrue;}else{head.flag=true;head=head.next;}}returnfalse;}
- 时间复杂度：O(n)
- 空间复杂度：O(1)