LeetCode-142-环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？

解题思路：

1. 本题属于发现环的起始点问题；
2. 如果链表中存在环，用快慢指针，快指针每次走两步，慢指针每次走一步，一定会在环内相遇，此时令慢指针指向head，重新开始前进，两个指针都每次走一步，相遇点，即为环的起始点。

Python3代码：

# 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:

        if not head or not head.next:
            return None

        fast = head 
        slow = head 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        
        if not fast or not fast.next:
            return None

        slow = head
        while slow!=fast:
            slow = slow.next
            fast = fast.next

        return slow