自我总结：Leetcode 141&142. 环形链表（快慢指针）

链表还有一种比较神奇的算法就是快慢指针。慢指针一次走一步，快指针一次走两步。

快慢指针目前发现用在两个链表的地方。一个是链表找中点，一种是环形链表。

先讲一下第一种：

找中点

快指针和慢指针都初始化在head上。快指针=fast；慢指针=slow。因为快指针一次走两步，慢指针一次走一步，所以当链表不是环形链表的时候，快指针一定会走到nullptr。当快指针走到nullptr或者fast->next == nullptr时，slow就指在了正中间（奇数长度）或者前半段的最后一个node（偶数长度）。

class slowAndFast{
    public:
        ListNode* findMiddle(ListNode* head){
            if(head == nullptr) return nullptr;
            ListNode* fast = head; ListNode* slow = head;
            while(fast->next->next!=nullptr && fast->next!=nullptr){
                fast = fast->next->next;
                slow = slow->next;
            }
            if(fast->next!=nullptr){
                fast = fast->next;    
            }
            return slow;
        }
}

注意：这里面的特殊情况就只有链表过短或者fast指不到最后。上例slow指到中点（奇数长度）或前半段的最后一位（偶数长度）。并且fast指针指向最后一位。

找中点做法会经常被用到，比如判断回文链表（234），重排链表（143）等等。

环形链表

环形链表经典的题型就是找有没有环，环的起始点的坐标是几。

这里借用一下官方解答的图

同样，fast指针一次走两步，slow指针一次走一步。起始都在链表的头部。

当fast和slow再次相遇的时候，一定有环形链表。相遇在B点，而这个时候我们假设快指针走了n圈了。

快指针走过的路就是 a+n(b+c)+b，慢指针走过的路就是a+b。（以下为证明慢指针一定没有走一圈：因为fast和slow的速度差为1，所以可以看成在slow刚入环时就开始不动，fast每次向前走一步，走了B步到了环的开头。因为速度差为1，所以一定不会一步跨过去，一定会慢慢追上的。当把slow看成不动，fast每次走一的情况下，最坏情况是要走环长减一次，最好是直接撞上。所以0<=B<=circle length - 1。C+B = circle length。所以1<=C<=circle length。）

综上，因为fast走的步数为slow的两倍，所以 a+n(b+c)+b = 2a+2b。所以nb+nc = a+b = n(b+c)。所以这个时候新建一个pre，在head的位置，让pre和slow都每次走一，slow因为进了环，所以一定一直在环里走。当pre走到环开始的位置的时候，pre走了a步。因为有上公式 a+b = n(b+c)，所以slow也走了a步，a还等于 n倍的（b+c） 环长减b，所以当pre和slow相遇时，就是环的入口。

这个时候加一个计数器就能知道a有多长了。

这个办法一般能解决环形链表里面最大的问题，就是有没有环，环的开始在哪。

题是Leetcode 141和142。等再做到了回来补充一下还有哪里有环形链表的题。