思路:使用快慢指针,快指针每次走两步,慢指针每次走一步,如果有环,则一定会快慢指针指向同一结点;
假设环的长度为n,先让一个指针走n步,另一个再开始走,当他们指针指向同一结点时,该结点就是环入口点
(在快慢指针相遇之后,慢指针指向表头,快指针留在相遇点,二者以每次一步走直到相遇,该相遇点就是环入口结点);
找到环入口结点之后,从入口结点开始遍历,每次遍历长度加一,如果下个结点等于入口结点,则返回长度
class ListNode(object):
def __init__(self, dataval):
self.dataval = dataval
self.next = None class JudgeLinkRing(object):
def is_link_ring(self,head):
if head is None or head.next is None:
return
slow,fast=head,head
while fast and fast.next:
slow=slow.head
fast=fast.next.next
if slow==fast:
slow=head
while slow !=fast:
slow=slow.next
fast=fast.next
fast1=fast
fast=fast.next
n=1
while fast1 !=fast
fast=fast.next
n=n+1 return slow,n return