快慢指针算法

快慢指针算法（Hare and Tortoise Arithmetic）是一种判断一个链表中是否有环路的算法。

慢指针每次走一步，快指针每次走两步（可以是任意长>1的步数），当有回路的时候，两个指针必然有相等的时候。

时间复杂度为O(n)

LeetCode 第141题 （模板）

bool hasCycle(ListNode *head){
    if (head==NULL||head->next==NULL) {
        return false;
    }
    ListNode *slow=head;
    ListNode *fast=head->next;
    while(fast!=NULL&&fast->next!=NULL){
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow) return true;  
    }
    return false;
}

LeetCode第142题

//前面和模板基本一样
//主要目标为寻找入口点
slow=head;
while(slow!=NULL&&fast!=NULL){
    if(fast==slow) return slow;
    slow=slow->next;
    fast=fast->next;
}
return NULL;

入口的数学证明 假设C点为相遇点，此时头节点到入口距离为1（AB），入口到相遇点的距离为1（BC），相遇点到入口的距离为3（CB），环长为4=BC+CB。

在相遇时，快指针走过的步数=AB+BC+n（BC+CB），慢指针的步数=AB+BC。快指针每次走 2 步，慢指针每次走 1 步=> AB+BC+n（BC+CB）=2*（AB+BC）。AB= (n-1) * (BC+CB)+CB ，说明同时从头节点和相遇节点出发的两个指针，每次走 1 步，最终会在入口处相遇。