快慢指针

一般用来解决链表中的一些问题

首先可以用来判断一个链表是否有环

环形链表（141）

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

还可以用来判断环的入口位置

环形链表II(142)

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = head
        if not head: return None
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                left, right = head, fast
                while left != right:
                    left = left.next
                    right = right.next
                    return left
        return None

注意：在第10行时，使用while True时，不能落下该点即为入口点的情况，如下列代码第10行所示

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = head
        if not head: return None
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                left, right = head, slow
                if left == right:
                    return left
                while True:
                    left = left.next
                    right = right.next
                    if left == right:
                        return left
        return None

分析：

为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇，而不会永远的错开

在相遇前的一步，永远会是下面的情形（fast指向node_1, slow指向node_2）下一步会同时指向node_3:

fast slow

node_1 -> node_2 -> node_3 -> node_4

快节点相对于慢节点的相对速度是1，相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

找环的入口

有环的情况可以抽象为上图所示：

相遇时：
slow指针走过的节点数为: x + y
fast指针走过的节点数： x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为环圈内节点的个数

而fast指针走过的节点数 = slow指针走过的节点数 * 2

(x + y) * 2 = x + y + n (y + z) 即： x + y = n (y + z)

要求的是x，因为x表示头结点到环形入口节点的的距离。

x = n (y + z) - y

在从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针

n=1时，fast指针在环形里转了一圈之后，就遇到了 slow指针了。公式变为 x = z

即从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

链表的中间节点(876)

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow