快慢指针 “体育中考”版

你好，这是我的第一篇博客，写博客是为了梳理知识，同时帮助大家，以下有问题请提出来，要喷的话请指出喷的点。共进，共勉！

请大家回忆体育中考惨痛的历史，那么直接开启故事。

故事

  由于四五月份的到来，我们也迎来了体育中考，其中最害怕的是1000米—300米跑道。体育中考当天，我和我的同学们现在同一起跑线，此刻，我们正在等待发令，“砰”的一声，我们一齐出去了，跑在领先的是我们班的体育生，外号“XX中学博尔特”，拥有一米八的身高，刀刻般的肌肉，他的步幅是我们的两倍，他第一个弯道要转直线了，我们还在300米起点，很少有人紧跟他。过了一分钟他跑完400米了，虽然我的目光在前，但是我的余光看见他马上要追上我了，又过了半分钟，我听见紧促的脚步声，他跑在了我的前面，我的懦弱感油然而生，他在弯道把我套圈了，之后，1000米跑完了。至此，惨痛的经历结束了。下面展示主角。

快慢指针

使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast指针向后移动两个位置。

应用

来看第一个例题

力扣 141.环形链表

如何去进行判环？
  就跟我被体育生给套圈一样的原理，1000米不是直接一条直线跑，而是围绕着，以相对去衡量，我每秒跑一步，体育生每秒两步，而其中有漏洞，当体育生身体力竭，我被喜欢的女生看见了，激发了我的潜力，体育生就套不了我圈。但是在计算机里面，它不能因为其它因素导致跑步中变速，它以绝对速度运动，不然死环，这就是为什么体育生一定能相遇到我（前提是要绕着跑道一直跑）
  说明判环只要我的快慢指针相遇就行了，相遇不了就没有环。

下面呈现代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
struct ListNode *q=head,*p=head;
    while(q&&q->next){
        p=p->next;
        q=q->next->next;
        if(p==q) return true;
    }
    return false;
 }

第二个例题

力扣 142.环形链表ll

找环的入口处

  比较300米跑道，意思是说我们只要找到300米的起始处就行了，下面数形理解

  那么假设到起跑处到环的入口距离为a，即我先跑到了300起点。

  整个环为x，体育生步长为2，即体育生跑了2a的距离

  剩下环的距离为x-a

  那么我与体育生都在环中，找体育生与我相遇的位置，怎么找？体育生要追到我，就是体育生来套我圈的这个过程，每一轮体育生步长大我一步，也就是体育生经过剩下（x-a）轮，（x-a）轮就能套我圈了。

  起点到相遇处为x-a，那么剩下的长度为a

  发现相遇处到环的入口与起跑处与环的入口距离相等，那么其中体育生重新到起跑处，再让他跟我相同的步长跑，我与体育生携手就可以到达终点。比较完美的结果。

  把我跟体育生转换成快慢指针，起跑处转换成链表头，那么这道题就不攻自破了

下面呈上代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head,*slow = head;
    while(fast && fast->next){
        slow = slow->next;
        fsast = fast->next->next;
        if(fast == slow)break;
    }
    if (slow == NULL || fast->next == NULL)
        return NULL;
    slow = head;
    while(fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

这就是关于快慢指针的介绍，欢迎交流讨论~