环形链表-力扣
一、题目描述
题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
二、题解
解题思路：
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环，则一定会在环中相遇，否则快指针率先走到链表的末尾。
扩展：
1、为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
2、快指针一次走3步，走4步，...n步行吗？
所以解决该题时，我们使用快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环，则一定会在环中相遇。
三、代码
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next !=null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
}另一种写法：
public boolean hasCycle2(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next !=null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
break;
}
}
if (fast == null||fast.next == null) {
return false;
}
return true;
}