数据结构-为什么双指针法可以用来解决环形链表？-使用O(1)的空间复杂度去解决环形链表的思路

前言

本篇讲解环形链表的解决方法与证明方法

一、环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/

本题实际有多种解决方法，我们在此仅讲解一种能够将空间复杂度控制在O(1)的解法

首先，我们观察题目，假定这个链表是环形链表的话，我们定义一个指针，一步一步地往下走，那么该指针必然会在环内循环，此时如果我们再定义一个指针，从起始点开始走，那么必然也会进入环，并且有几率与前面的指针相遇

这就转化成了我们中学时常见的物理问题——追及问题

追及问题中，往往是一者快一者慢，那么我们为了分辨，便可以使用双指针法，定义一个快指针fast，一个慢指针slow，两者均从起点开始走，fast一次走两步（即两个结点），慢指针一次走一步，那么当两者都进入环之后，就会在环内循环，并且必然会相遇，而两者相遇，就代表这个链表是环形链表。因为如果这个链表是一个普通的不带环链表，那么指针必然会走到空，并且快指针fast必然会先慢指针一步走到空

因此，我们可以使用双指针法来解决问题

二、代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* low = head;
    if(head == NULL)
        return false;
    struct ListNode* high = head->next;
    if(high == NULL)
        return false;

        while(high != low && high != NULL && high->next != NULL)
        {
            high = high->next->next;
            low = low->next;
        }
    
    if(high && high->next)
        return true;
    else
        return false;
}

三、证明

上面我们提到了可以使用双指针法来解决问题，那么我们不免会提出一个疑问：为什么快指针fast一次走两步，慢指针slow一次走一步一定会相遇？它们不会错过吗？为什么？如果fast一次走三步，走四步，怎么办？

下面我们对这个问题进行讲解、证明

当fast一次走两步，slow一次走一步时，相遇情况

如图，我们先以fast一次走两步，slow一次走一步的情况进行证明

当slow进环时，fast已经在环里走了一段距离了，并且在追及问题中，必然是fast追上slow，而不是slow追上fast，所以此时我们假定两者间的距离为N

因为fast一次走两步，slow一次走一步，并且fast走的是比slow快的，在追及问题中，必然是fast追上slow，因此我们可以从距离N入手

此时，两者若同时移动一次，两者间的距离便会缩小1，因此两者间的距离便会从N变为N - 1，再变为N - 2，每移动一次就会减1，直到两者相遇距离变为0停止，那么两者必然会相遇

距离变化如图：

当fast一次走三步，slow一次走一步时，相遇情况

如果当fast一次走三步，slow一次走一步，又会发生什么呢？

如图，我们仍然记slow刚进环时，两者间的距离为N

而当fast一次走三步，slow一次走一步时，两者每同时走一次，两者间距离便会减少2

如图可知：若N为偶数，两者会相遇，若N为奇数，两者会错过，不会相遇

那么我们可以记，当N为奇数时，两者间的第一次追击失败，不会相遇，开始第二轮追击

（注意：在此时，我们讨论的是只有两者间的距离为0才算相遇，fast一次走两步，不是一步一步走，而是直接跳到两步的位置）

如图所示，此时fast与slow的位置关系为距离-1

但是我们要讨论的是fast追击slow，那么记环的周长为C的话，两者间的距离就会从N变为C - 1，此时开始新一轮的追击，那么我们就要对C进行讨论

当C为奇数时，C - 1为偶数，两者间的距离每次减2，可以相遇；

当C为偶数时，C - 1为奇数，两者间的距离每次减2，错过，不会相遇，距离还会变为-1；此时，又进入了新一轮的追击，而距离仍然是C - 1，但是与上一次追击相同，C - 1仍然为奇数，还是会错过，不会相遇，错过之后新一轮追击的距离仍然是C-1

因此，当C为偶数时，两者之间会进行重复的追击，并且每次相差的距离都是相同的，陷入了循环，因此两者永远不会相遇。

当fast一次走四步，slow一次走一步时，相遇情况

当fast一次走四步，slow一次走一步时，两者间的距离会每走一次便减少三

我们继续沿用上面的图，此时我们已经知道，要对两者间的距离N进行讨论

而每次减少3，那么就要看N是否为三的倍数，情况会有三种，

第一种：N = 3k，k≥0

此时slow与fast每同时走一步，距离N减少3，必然会相遇

第二种：N = 3K + 1,K≥0

此时slow与fast每同时走一步，距离N减少3，当两者间的距离为1时，再同时走一步，变为-2，那么该轮追击失败，进入下一轮追击

而沿顺之前的思路，此时两者间的距离便会变为C - 2，此时就要对C进行讨论

当C = 3k时，两者间的距离N1 = C-2 = 3K-2 = 3(k - 1)+ 3 - 2 = 3(k - 1) + 1 = 3k + 1
（注：k只是一个变量，相当于函数中的x，替换即可，因此k-1与k并无不同，便于理解可将k视为x），此时新一轮追击中，N1每次再减少3，最后距离仍变为-2，即C - 2，相当于进行重复操作，陷入了循环，因此两者不会相遇

当C = 3K + 1时，两者间的距离N1 = C - 2 = 3K + 1 - 2 = 3K - 1 = 3K + 2;

此时新一轮追击中，N1每次减少3，最后距离为-1，即C-1，不会相遇；
进入新一轮追击，因为C = 3k+1，那么新距离N2 = C - 1 = 3K + 1 - 1 = 3K，每次移动时N2减少3，可以相遇

当C = 3K + 2时，两者间的距离N1 = C - 2 = 3K + 2 - 2 = 3K；
此时新一轮追击中，N1每次减少3，可以相遇

第三种：N = 3K + 2,K≥0

我们沿顺上一种情况的思路即可。

此时slow与fast每同时走一步，距离N减少3，当两者间的距离为2时，再同时走一步，变为-1，那么该轮追击失败，进入下一轮追击

而沿顺之前的思路，此时两者间的距离便会变为C - 1，此时就要对C进行讨论

当C = 3k时，两者间的距离N1 = C-1 = 3K-1 = 3(k - 1)+ 3 - 1 = 3(k - 1) + 2 = 3k + 2
此时新一轮追击中，N1每次减少3，最后距离为-1，即C-1，不会相遇；
进入新一轮追击，因为C = 3k，那么新距离N2 = C - 1 = 3K - 1 = 3K + 2，相当于进行重复操作，陷入了循环，因此两者不会相遇

当C = 3K + 1时，两者间的距离N1 = C - 1 = 3K + 1 - 1 = 3K；
此时新一轮追击中，N1每次减少3，可以相遇

当C = 3K + 2时，两者间的距离N1 = C - 1 = 3K + 2 - 1 = 3K + 1；
此时新一轮追击中，N1每次再减少3，最后距离仍变为-2，即C - 2，不会相遇；
进入新一轮追击，因此C = 3K + 2，那么新的距离N2 = C - 2 = 3K，N2每次减少3，可以相遇

总结：

当fast一次走两步，slow一次走一步时，每同时走一次，两者间的距离便会减少1，因此无论N和C是偶数还是奇数，两者必然会相遇

当fast一次走三步，slow一次走一步时，每同时走一次，两者间的距离便会减少2
因此当N为偶数时，可以相遇

当N为奇数时，对环的周长C进行讨论，当C为偶数时，永远无法相遇；当C为奇数时，两者会相遇，此时要追击两次

当fast一次走四步，slow一次走一步时，每同时走一次，两者间的距离便会减少3
因此当N = 3K时，可以相遇

当N = 3k + 1时，需要对C进行讨论，当C = 3k时，不会相遇；当C = 3K + 1时，可以相遇，此时要追击三次；当C =3K+ 2时，可以相遇，此时要追击两次

当N = 3K + 2时，需要对C进行讨论，当C = 3k时，不会相遇；当C = 3K + 1时，可以相遇，此时要追击两次；当C = 3K+2时，可以相遇，此时要追击三次

如图：
1.当fast一次走两步，slow一次走一步时，总会相遇

2.当fast一次走三步，slow一次走一步时：

3.当fast一次走四步，slow一次走一步时：

总结

本篇主要讲解了如何用O(1)的空间复杂度解决环形链表的问题，同时证明了为什么可以用双指针法去解决，后面会继续讲解环形链表的一个推论