142环形链表II

# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

# 这道题我们还是用双指针的办法,快指针f一次走两步,慢指针s一次走一步。
# 如果两个指针相遇,那么代表链表有环,不相遇就直接返回好了。
# 下边我们讨论有环的情况下找到环的入口。
# 快慢指针第一次相遇的时候 f = 2s
# 假设链表长度为 a + b ,a为从头部节点到环入口的长度。
# 那么f和s都走过一次a,f = a + n1*b , s = a + n2 * b
# n1一定是n2的倍数。
# f - s = (n1 - n2 ) b = s
# 我们让 n = (n1 - n2) 可得 f = 2nb s=nb
# 我们观察链表可以看到,如果我们从链表的头部开始走,走到环的入口(需要完整走完链表)需要k步
# 那么 k = a + n3b # 这里n3 可以取任意整数,因此我们让n3 为n
# k = a + nb 现在慢指针已经走了nb步了, 因此我们让头指针在走a步,就能够和慢指针在环的入口相遇了。
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast,slow = head,head
while fast and slow and fast.next :
fast = fast.next.next
slow = slow.next
if fast == slow :
break
else:return
count = 0
while head != slow:
count += 1
head = head.next
slow = slow.next
return head
原文地址:https://www.cnblogs.com/cong12586/p/13790369.html