LeetCode0141.链表循环[易][Python][双指针]题目英文题目地址给定一个链表，判断它里面是否有一个循环。要表示一个循环在对于给定的链表，我们使用整数pos表示tail连接到的链表中的位置（从0开始）。如果pos为-1，则链表中没有环。例1：输入：head=[3,2,0,-4],pos=1输出：true解释：链表中有一个环，tail连接到第二个节点例2：输入：head=[1,2],pos=0Output:true解释：链表中有环，tail连接第一个节点。例3：输入：head=[1],pos=-1Output:false解释：链表中没有环链表。跟进：你能用O（1）（即常量）内存解决它吗？为了表示给定列表中的循环，我们使用整数pos来表示列表中尾部连接的位置（索引从0开始）。如果pos为-1，则列表中没有循环。示例1：输入：head=[3,2,0,-4],pos=1输出：true解释：链表中有一个环，其尾部连接到第二个节点。示例2：输入：head=[1,2],pos=0输出：true解释：链表中有一个环，其尾部连接到第一个节点。示例3：输入：head=[1],pos=-1输出：false解释：链表中没有循环。更进一步：你能用O(1)（即常量）内存解决这个问题吗？思路是用快慢双指针来表示快慢指针。快指针的速度设置为慢指针的两倍。如果链表中有环，则快慢双指针必须相遇。请在此处查看证明。空间复杂度：O(1)Python代码#Definitionforsingle-linkedlist.#classListNode(object):#def__init__(self,x):#self.val=x#self.next=NoneclassSolution(object):defhasCycle(self,head):""":typehead:ListNode:rtype:bool"""ifhead==None:returnFalseslow,fast=head,head#快慢双指针whilefast.next!=Noneandfast.next.next!=None:#必须是fast.next和fast.next.nextslow=slow.nextfast=fast.next.next#fast快指针速度是慢慢指针的两倍ifslow==fast:#如果链表有环，fast和slow会相遇returnTruereturnFalse代码地址github链接
