• 介绍
• 判断链表是否有环
• 返回一个存在环路的链表中环路开始的位置
• 判断链表是否是回文链表

链接：https://zhuanlan.zhihu.com/p/72886883

介绍

快慢指针方法也被称为 Hare & Tortoise 算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。

该算法的应用场景：

• 处理链表或数组中的循环的问题
• 找链表中点或需要知道特定元素的位置

何时应该优先选择这种方法，而不是上面提到的二指针方法
有些情况不适合使用二指针方法，比如在不能反向移动的单链接链表中。使用快速和慢速模式的一个案例是当你想要确定一个链表是否为回文（palindrome）时。

判断链表是否有环

返回一个存在环路的链表中环路开始的位置

首先， 用快慢指针我们可以判断出链表中是否有环， 假设在z 点 fast指针和slow 指针相遇。x-y 长度为a， y-z 长度为 b ， z-y 长度为c。

则：slow 指针走了 a+b 的距离。 fast 指针走了 a + n（b + c）+ b 的距离。（可能不仅绕了一圈而是绕环走了n圈）

fast指针的速度是slow 指针速度的2倍。 所以a + b + n（b + c） = 2 （a + b）， 简化得 a+b = n（b + c）。 因为我们想要求 a 的距离， 所以我们移动方程 得到 a = （n-1）b + n c 。

仔细观察上面的等式。 考虑它的含义， 即c 总比b 多一次， 这就意味着， 我们再放两个指针， first放在x ，second放在z ，这次保持速度一致， first 跑到y ， second 也会跑到y。所以，当它们相遇，就是cycle的起点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow=head;
        ListNode* fast=head;

        //do-while
        do{
            if(!fast||!fast->next)
                return NULL;
            fast=fast->next->next;
            slow=slow->next;
        }while(fast!=slow);

        //此时可以确定有环
        slow=head;  //任意一个皆可
        while(slow!=fast){
            slow=slow->next;
            fast=fast->next;
        }

        return slow;
    }
};

判断链表是否是回文链表

利用快慢指针找到中间指针
利用速度关系，快指针=2*慢指针，当快指针到末尾时，慢指针即为链表中点。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next)
            return true;
            
        ListNode* slow=head;
        ListNode* fast=head;

        //slow为中间的偏右 1 2 3 4 5 NULL
        //&&
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;          
        }

        //反转后半部分链表
        ListNode* p=slow;
        ListNode* q=slow->next;
        while(q){
            ListNode* tmp = q->next;
            q->next=p;
            p=q;
            q=tmp;
        }
        slow->next=NULL;

        while(p){
            if(p->val!=head->val){
                return false;
            }
            p=p->next;
            head=head->next;
        }

        return true;
    }
};