给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。 进阶： 你是否可以不用额外空间解决此题？ # Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution(object): def detectCycle(self, head: ListNode)-> ListNode: if head is None: return None slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if fast == slow: break # 若fast或fast.next 为空，则没有环，否则，相遇，有环 if fast is None or fast.next is None: return None slow = head while slow != fast: slow = slow.next fast = fast.next return fast def detectCycle2(self, head): """ :type head: ListNode :rtype: ListNode """ s = {None} while head not in s: s.add(head) head = head.next return head if __name__=='__main__': s = Solution() head = ListNode(1) head.next = ListNode(2) head.next.next = ListNode(3) head.next.next.next = ListNode(4) head.next.next.next.next = ListNode(5) head.next.next.next.next.next = head.next.next ''' [1]-[2]-[3]-【4】 \ | \ | \[5] slow 每次走一步，fast 每次走两步 ， 相遇在[4]，slow总共走了3步，fast走了6步 1 2 3 4 1 2 3 4 5 3 4 可以看出fast比slow多走了5 3 4 这个环， f = 2 * s ; s + w = f = 2 * s ; -> w = s head到环的起点+环的起点到他们相遇的点的距离 与 环一圈的距离相等 --> head运行到环起点 和 相遇点到环起点 的距离也是相等的 ''' print(s.detectCycle(head).val)
