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