请注意,本文编写于 272 天前,最后编辑于 272 天前,内容可能已经不具有时效性,请谨慎参考。
描述
判断给定的链表中是否有环。如果有环则返回true,否则返回false。
你能给出空间复杂度的解法么?
输入分为2部分,第一部分为链表,第二部分代表是否有环,然后回组成head头结点传入到函数里面。-1代表无环,其他的数字代表有环,这些参数解释仅仅是为了方便读者自测调试
示例1:
输入:{3,2,0,-4},1
返回值:true
说明:
第一部分{3,2,0,-4}代表一个链表,第二部分的1表示,-4到位置1,即-4->2存在一个链接,组成传入的head为一个带环的链表 ,返回true
思路
如上图就是一个环形链表,他是有一个闭环的,他有一个特性:那就是如果顺着链表一直往前走,永远也走不到头。
这个特性一会证明链表是否有环的时候会用到。
咱们想想这么一个场景:在操场跑圈的时候,一个跑的快的人如果跑的时间够长最后会超过跑的慢的人。因为操场是一个环形,没有尽头。同样如果一个链表如果是环形的,同理可以用两个指针去链表上跑一跑,也就是快慢指针,不就可以了。
代码
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;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
}
}
Q.E.D.