台中市网站建设_网站建设公司_Python_seo优化

1.思路：快慢指针法。如果链表有环的话，快指针一定可以在一段时间后追上慢指针，这两个指针一定会相遇。

2.注意：代码比较两个节点的时候，比较的是内存地址是否一致，并没有比较节点的val。

3.疑问。

（1）快指针会不会跳过慢指针，从来不会和慢指针相遇呢？

答：

这是不可能的。如果由有环的话，那么快慢指针都会进入到环中。这个时候用“相对速度”思考，慢指针不动，快指针相对于慢指针每次只走一步，那么快慢指针一定会相遇。

（2）为什么代码里的while循环并没有判断slow是否为空？

答：

slow在fast的后面，如果fast不为空，那么slow也肯定不为空。也就是fast在探路，slow走的都是fast走过的路。

4.复杂度分析：

（1）时间复杂度：O(n)，其中n是链表的长度。

（2）空间复杂度：O(1)。

附代码：

public class Solution { public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if(fast == slow){ return true; } } return false; } }