python实现leetcode之142. 环形链表 II

解题思路

两步走：
第一步，检测是不是有环，使用快慢指针
第二步，再从头开始一个慢指针，第一步的慢指针继续

假设第一步走了n轮，即slow经过了n个节点，那fast就经历了2n个节点
则，在第二步中，再继续n轮，slow就到fast的位置，head就到slow第一步结束的位置，此时相遇
此时slow和head同时退x个节点到他们第一次相遇的位置，就是我们循环的条件

142. 环形链表 II

代码

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast: break
        # 至此，slow看过了n个结点，fast看过2n个结点
        # 如果重新从头开始一个结点head，与slow同样的速度
        # 过了n个结点之后，slow就是之前的fast，head只就是slow，显然相遇
        if fast and fast.next:
            while head != slow:
                head = head.next
                slow = slow.next
            return head
        else:
            return None