思路：

快慢指针，也就是龟兔赛跑

 

代码：

public class Solution {
    public boolean hasCycle(ListNode head) {
		if(head==null||head.next==null){
			return false;
		}
		ListNode slow=head;
		ListNode fast=head.next;
		
		while(slow!=fast){
			if(fast==null||fast.next==null){
				return false;
			}
			slow=slow.next;
			//虽然会走到null，但再一次循环后会判断fast为null
			fast=fast.next.next;
		}
		return true;
    }
}

 

分解：

1）使用的其实是Floyd判圈算法（龟兔赛跑算法）

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

 

慢指针每次走1步，快指针每次走2步

 

2）循环退出条件是slow==fast

 

复杂度分析：

时间复杂度：O（N）

空间复杂度：O（1）