目录摘要一快2 慢1二快3 慢1三公式推演摘要本博客旨在讲清楚在成环链表中使用快慢指针时无论快指针多快都一定会在环内相遇一快2 慢1最常见的就是快指针fast步长为2慢指针步长为1可以从两个角度理解为什么一定相遇角度1由上图假设当slow刚进入环时此时fast和slow的距离为N此时二者开始移动因为fast步长为2慢指针步长为1这意味着以fast追逐slow的视角来看它们之间的距离会以每轮1个节点的距离缩小则二者之间的距离一定会逐1递减到0所以一定相遇角度2一开始fast和slow之间的距离为N则N-1N-2N-3.....32,1,0,一定会为0代表相遇看完这两个角度难免会有这种想法Q若快指针fast步长为3慢指针步长为1岂不是就无法相遇了因为它们之间的距离会以每轮2个节点的距离缩小所以N-1N-2N-3最后可能3,1,-1就会导致错过了如下图A但实则慢指针步长为1不管fast步长为多少只要入环则一定会相遇二快3 慢1所以第二大点我们就分析下fast步长为3慢指针步长为1的情况是可能相遇还是不可能相遇还是一定相遇我们假设当slow刚进入环时此时fast和slow的距离为N假设C是环的长度上文分析过N为奇数对于快3 慢1的情况第一轮是肯定无法相遇的会错过错过的一瞬间此时他们之间的距离变成C-1(fast超过slow一个位置会开始新一轮的追击那新一轮的追击的结果就需要讨论了首先需要注意的是当slow指针入环的时候此时的fast和slow之间的距离为N此轮追击和上述的新一轮追击是不同的因为入环时候的距离受整个成环链表的结构的影响所以对于不同的成环链表一开始的N是不同的而新一轮追击则是一定和C-1有关总结如果 N是奇数第⼀轮快追上时会错过距离变成-1即C-1进⼊新的⼀轮追击而新一轮的追击距离为C-1此时就好比N 为 C-1所以①C-1如果是偶数那么下⼀轮就追上了②C-1如果是奇数 那么就永远都追不上因为又回到了N为奇数的情况了此时可能会有这样的疑问Q如果新一轮追不上距离C-1是奇数那此轮再次错过后的新距离有没有可能变成偶数从而下次就能追上了A不可能如果C-1是奇数且从距离C-1开始追击则永远无法相遇因为C-1为奇数代表C-3C-5C-7...都是奇数所以最后最接近slow的时候为1这个奇数此时再相减为-1又回到了循环一句话一个奇数逐2递减每个值都会奇数不可能减到0的如11--9--7--5--3--1---1所以到这里我们貌似已经很严谨的分析出来快3 慢1的快慢指针在成环链表中情况如下将上图转换成另一种角度的理解总结追不上的前提条件 N是奇数C是偶数三公式推演根据下图推演公式设环的周长为C入环前的长度为L当slow指针刚进入环时此时fast和slow的追赶距离为N并且我们不知道fast已经在环内绕了几周 说不定该链表结构的L很长C较短导致当slow进入环之前fast已经绕环n圈了(n倍的C)所以可得slow走的距离Lfast走的距离LC-NnC但不管如何fast指针走的路程一定是slow的3倍因为快3慢1所以3LL nC C − N------2L (n 1)C− N注这个式子是slow 入环那一刻slow 和 fast 之间的路程等式是一定成立的最终得到2L (n 1)C − N首先2L一定是一个偶数因为2乘奇数或偶数结果都为偶数那我们就可以根据差为偶数分析出(n 1)C 和 N这两项的奇偶数情况解释差为偶数有两种情况①要么是被减数和减数都是偶数得到的差为偶数②要么是减数和减数都是奇数得到的差为偶数③其他情况得到的差都为奇数此时回看我们之前的分析对快3 慢1中的N为奇数时导致刚进环的轮次fast错过了slow然后我们新一轮距离C-1的奇偶性的分析N已经确定为奇数在上述公式中当N为奇数此时让差2L为偶数则(n 1)C一定为奇数那(n 1)C这一项整体为奇数则代表积为奇数则被乘数和乘数都必定为奇数所以C一定只能为奇数首先2L (n 1)C − N是恒成立的根据分析当N为奇数时C也只能为奇数才会成立所以在对快3 慢1中的N为奇数时导致刚进环的轮次fast错过了slow然后我们新一轮距离C-1的奇偶性的分析中只会存在N和C都为奇数然后相遇的场景不会出现N为奇数C为偶数不会相遇的场景而快指针⼀次⾛4、5.....步最终也会相遇证明同上.....