【经典面试题】环形链表-3.面试加问

时间:2024-07-12 21:53:21

当然面试题不会这么容易,面试官随之抛下以下两个问题:
1.有没有可能快慢指针永远无法相遇呢?
2.如果快指针一次走3步,一次走4步,一次走n步还会不会相遇呢?

经过简单思考可以得出:当快指针一次走两步时,快慢指针每次行动的间隔值为1,那么此时当慢指针进入圆环开始被快指针追击时,必定会被追上。

那么如果快指针一次走三步呢?

有没有可能慢指针和快指针永远无法相遇呢?
这里进行简单的数学证明:

在这里插入图片描述
简单画图分析:
设链表从开始到进入环的长度为L,两指针在距换开始点的N的长度相遇,环长为C
从中可以得到哪些数学的等量关系式呢?
已知快指针的速度是慢指针的三倍,那么其走的路程也就是三倍,也就是每次追击两者之间的距离减少2

这里给出简单的思路图:
在这里插入图片描述
从图中可以看出

从图中可以看出当初始的N值为奇数时,且环长C为偶数时,两指针永远无法相遇。
那么现在就是要判断此种情况是否存在。

在这里插入图片描述
可推出此等式,从中我们可以发现,=左边为2L,永远为偶数,而右边为一个减式。
通过数学知识,我们得知当两数相减时,只有偶数-偶数或者奇数-奇数时得到偶数,所以当C为偶数时,(x+1)*C为偶数,此时N也为偶数,那么之前讨论的永远无法追上就时谬论了。
因此在进行第二轮追击时就可以追上,从而解得此题。

以及后面的快指针为4步N步都是同一解法。

如果被面试的是你,你答得出来吗?面试官先抛出一个简单代码题,随之考察面试者的数理分析能力,所以数学基础也是不可或缺的。

感谢大家的阅读,我将持续更新经典面试题。