链表是否有环

https://leetcode-cn.com/problems/linked-list-cycle/submissions/
判断链表是否有环 可以使用hashmap来存储是否之前有过
但是由于题目要求只能o1的空间复杂度
所以使用快慢指针来处理该问题

需要注意的几点corner case,fast及slow node可能为空
如果有环则slow会追上fast, 如果没有的话fast.next为空节点.

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        if not slow:
            return False
        fast = head.next

        if not (fast and fast.next):
            return False

        while slow != fast and fast and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        
        if slow == fast:
            return True
        else:
            return False

https://leetcode-cn.com/problems/linked-list-cycle-ii/
获取环形链表的交叉位置，一样o1的空间复杂度
这里需要用一点证明
假设从最开始到交点的距离为x, fast和slow交点为y, 环剩下的距离为z
因为fast的速度是slow的一倍，所以fast的路径长度为slow的的一倍
（x + y）* 2 = x + n(y + z) + y
左右都去掉一个x + y, 则可得 x + y = n(y + z)
x = (y + z)n - y
x = (n-1)(y+z) + z
由于我们知道y+z为一圈，所以从相交点走z和从头开始走x相遇的地方就位环的相交点

# 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:
        current = fast = slow = head
        if not (fast and fast.next):
            return 
        
        # 这里因为slow和fast一样 所以需要先slow和fast都走一步再循环往前走
        fast = fast.next.next
        slow = slow.next
        while fast != slow and fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        if fast != slow:
            return
        
        while current != fast:
            current = current.next
            fast = fast.next
        
        return current