Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1: Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2: Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3: Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
给定一个链表，判断它是否有一个循环。 为了在给定的链表中表示一个循环，我们使用一个整数pos，它表示tail连接到的链表中的位置(0索引)。如果pos为-1，则链表中没有循环。
只要是有环的链表，我们采用快慢指针，那么它们总会可以遇见的。 以图片为例，假设环的长度为R，当慢指针walkerwalker走到环入口时快指针runnerrunner的位置如图，且二者之间的距离为S。在慢指针进入环后的tt时间内，快指针从距离环入口S处走了2t个节点，相当于从环入口走了S+2t个节点。而此时慢指针从环入口走了t个节点。
假设快慢指针一定可以相遇，那么有S+2t−t=nR，即S+t=nR，如果对于任意的S，R，n，总可以找到一个tt满足上式，那么就可以说明快慢指针一定可以相遇，满足假设(显然可以找到)
而实际上，由于S<RS<R，所以在慢指针走过一圈之前就可以相遇
所以如果链表中有环，那么当慢指针进入到环时，在未来的某一时刻，快慢指针一定可以相遇，通过这个也就可以判断链表是否有环。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head==null || head.next==null) return false; ListNode fast=head; //快指针 ListNode slow=head; //慢指针 while(fast!=null){ //fast一次走两步，slow一次走一步 if(fast.next!=null&&fast.next.next!=null){ fast=fast.next.next; slow=slow.next; }else{ return false; } //两个相等说明相遇，不能放上面，因为一开始进来两个都是头结点 if(fast==slow) return true; } return false; } }