题目描述

blablabla

样例

blablabla

算法1

快慢指针扫描时间复杂度 $O(n)$

1、判断是否存在环

快指针一次走两步，慢指针一次走一步

若存在环，则两指针必会相遇

2、存在环后让慢指针回到起点

由于快指针比慢指针多走了k步，而这k步正好是环的长度，

设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。如果从相遇点继续前进 k - m 步，也恰好到达环起点。

所以可以让两指针以同样的速度前进，相遇点即为环的起点

Python3 代码

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

class Solution(object):
    def entryNodeOfLoop(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast = slow = head
        has_cycle = False
        while fast is not None and fast.next is not None:
            fast = fast.next.next   # 快指针一次走两步
            slow = slow.next        # 慢指针一次走一步
            if fast == slow:        # 若存在环，则两指针必会相遇
                has_cycle = True
                break
        if not has_cycle:
            return None
        else:
            slow = head             # 判断存在环后，让慢指针回到起点
            while slow != fast:
                slow = slow.next    # 快慢指针
                fast =  fast.next
            return slow