Home > Archives > 如何判断链表中是否存在环路

如何判断链表中是否存在环路

在实习面试中,这个问题出现的频度很高,我在这里总结一下。

方法一,在链表中增加一个域visited,都初始化为0,表示此节点都未被访问。从链表的头部开始走,每走过一个链表就标记visited为1,如果要访问的下一个节点的visited域为1,那么证明链表中有环。

方法二,先考虑另外一个问题:在未知链表长度(长度为奇数)的情况下,如何找到链表中间的节点?可以这么办,设置两个指针p和q,初始时都指向链表的头结点。然后沿着链表,p走一步而q走两步,这样当q正好到达链表的尾节点的时候,p应该在链表的中间节点。

如何判断链表中有环也可以用这种思路,还是设置p和q两个指针,沿着链表走,p走一步而q走两步。如果链表中有环,则p和q会在某个时间相遇。我们来分析一下,在两个指针进入环路之前,肯定不会相遇,那么如果两个指针相遇,则一定是它们都在这个链表的环路之中。假设此时p点刚刚进入到链表中的环中,q在环中的某一个位置,如图所示。

如何判断链表中是否存在环路

设t时间后,p和q在环中的某一点相遇,初始时p和q相隔k个节点(0<=k<=n-1,其中n为环中的节点数,在这里为5;图中p和q相隔3个节点,而不是2个:因为假如q不动,p需要经过3步移动才可以和q重合),那么可得:t(mod n) = k + 2t(mod n),其中t(mod n)代表t除以n所得到的余数,t为正整数。那么显然,设m为正整数,t = mn - k,所以满足要求的最小的k为2(m = 1的时候)。这也就说明了,如果链表中有环,那么p和q在某个时刻一定相遇。

而p和q相遇,是否能说明链表有环呢?答案是肯定的,考虑其逆反命题,如果链表没有环,则p和q则永远不可能相遇。进一步说明了,在这种实验设置之下,p和q相遇是链表有环的充分必要条件。

声明: 本文采用 BY-NC-SA 授权。转载请注明转自: 孔明