leetcode142环形链表Ⅱ

题目

思路1

利用hash表，每当走到一个节点，判断该节点是否已经存在hash表中，如果存在，则该节点就是要求的节点，否则将其加入hash表，直到走到尾节点。

python中的set的底层实现就是hash表（与list的顺序存储不同，set效率要高于list，尤其是大数据查找下），所以可以直接利用set来进行操作。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        s = set([])
        while head:
            if head in s:
                return head
            else:
                s.add(head)
            head = head.next

时间复杂度空间复杂度都是O(n)。

思路2

Floyd算法

Floyd判圈算法，也称龟兔赛跑算法，可用于判断链表、迭代函数、有限状态机是否有环。如果有，找出环的起点和大小。时间复杂度O(n)，空间复杂度O(1)。

第一步：慢指针走1步，快指针走2步，如果不能相遇，说明没有环，否则找到快慢指针相遇的点。
第二步：慢指针指向头节点，快指针指向第一步中的相遇节点，两个指针都走一步，则它们再相遇的点就是环的入口！！！

证明

①在第一步中，快指针走的步数（F+a+b+a）是慢指针走的步数（F+a）的两倍（a+b+a是因为快指针一定是饶了环的一圈才遇到慢指针）。
所以有：

F+a+b+a = 2(F+a)
F+2a+b = 2F+2a
F = b
②所以第二步两个指针都走1步，则一定是在环的入口相遇。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head: return
        s, q = head, head
        flag = 0  # flag用来判断是否有环
        while q.next and q.next.next:  # 第1步
            s = s.next
            q = q.next.next
            if s == q:
                flag = 1
                break
        if not flag: return  # 无环返回None
        s = head  # 第2步
        while s != q:
            s = s.next
            q = q.next
        return s