LeetCode OJ 141. Linked List Cycle

时间:2023-12-27 18:45:13

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

解决这个问题需要很巧妙的思路,一般我们会想到观察链表中是否出现过重复出现的节点。但是这样的空间的复杂度是O(n),比如用set来存储出现过的节点,然后看下一个节点是否存在于set中。

一个很巧妙的解决办法是设置两个指针,一个快指针和一个慢指针。快指针每次移动两步,慢指针每次移动一步。假设两个指针同时从环的某一个节点出发,环的长度是N。由于快指针每次比慢指针快一步,所以至多N次移动后快指针比慢指针多移动N次,正好超过慢指针一环,也就是说N词移动以后两个指针肯定能相遇。而且不论两个指针是否是从环的同一个节点出发,两个指针都会在M次移动后相遇,且M<=N(M是指指针在环上的移动次数,由于链表中的前半段可能不在环上,所以两个指针到达环上节点的时间会有所不同,快指针会先到达,慢指针后到达)。代码如下:

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