判断一个链表是否存在环，有一个Floyd判圈法
tortoise = top
hare = top
forever:
if hare == end :
return 'No Loop Found'
hare = hare.next
if hare == end :
return 'No Loop Found'
hare = hare.next
tortoise = tortoise.next
if hare == tortoise:
return 'Loop Found' 这里的快慢指针分别用hare和tortoise来指代。
判定存在圈的条件是快慢指针重合，也就是上图中的乌龟和兔子能够走到一起去。
而本题我们要求返回这个链表环的入口结点。
网上的好多回答都是基于列未知数方程判定关系，如果在面试的过程中让我现场第一次推算这个过程（现在是会了，也是做的次数多了才记住了）我是不行的，必须得找到一个更加容易理解的方式。
这里我把环展开，让乌龟和兔子在展开的路上跑，兔子的速度是乌龟的二倍。
红色的代表环，分割线分割重复的环，也就是他们多跑一个环我就多展开一个，上图显示的就是他们所跑的真正路程。当乌龟距离入口的距离与兔子距离入口的距离相同的时候，他们就算是相遇了。
而且兔子跑的总路程应该是乌龟的二倍。
这时候我们派出另一只红色乌龟从头开始跑，当这红色只乌龟跑完a-b的路程的时候，绿色乌龟也跑到了a-b到达环的入口处了。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null) {
slow = slow.next;
if(fast.next == null) {
return null;
}
fast = fast.next.next;
if(fast == slow) {
ListNode node = head;
while(node != slow) {
node = node.next;
slow = slow.next;
}
return node;
}
}
return null;
}
} 
京公网安备 11010502036488号