检查链表是否有环,带数学推导

推导

给定下列列表(4指回2),若有快慢两个指针,慢指针每次前进一步,快指针每次前进两步,求两指针何处相遇?

1-2-3-4
  |___|

解:

设两指针前进n次。n必定大于等于1。

In[]:=Reduce[Mod[n – 1, 3] == Mod[2n – 1, 3], n, Integers]Out[]:=\(c_1\in \mathbb{Z}\land n=3 c_1\)

然后寻找满足上述条件(Out[1])的最小的n。

In[]:=FindMinimum[{3c, 3c > 1, Element[c, Integers]}, c]Out[]:={3., {c -> 1}}

所以n=3,即slow、fast两指针在4处相遇。

一般化:给定一个单链表,前面非循环部分有a个节点(长度为a),后面循环部分有l个节点(长度为l)。求快慢两指针走多少次后相遇?

同理,设前进n次后相遇。(n>a)

快指针的位置=慢指针的位置

\(\begin{align}
&(2n-a) \% l=(n-a) \% l  &\\
\Rightarrow &2n-a\equiv n-a \pmod{l} &\quad \text{公式1}\\
\Rightarrow & n \equiv 0 \pmod{l} & \quad \text{公式2}\\
\therefore & n=kl (k\geqslant  0) &
\end{align}\)

公式1是同余表达式,读作2n-a和n-a在模l下同余,\(\equiv\)不是全等的意思,mod不是5 mod 3=2的意思。公式2应用同余的性质,等号右边移到左边抵消掉。(注意到\(\pmod{l}\)前的空格没有?mod l表示对前面等号的左边和右边同时取余数)

所以n是l的倍数。n不一定等于l,因为n必须大于a,而a与l的关系未知。

因为\(n\neq l\),所以\(2n-n=kl\neq l\)。这里就证明了Bluefeather说的“fastVal – slowVal equals the size of the loop”[1]Bluefeather. Share my O(n) complexity and constant space code. Keep the original list. Any comments. . 2014-12-12 [2015-01-08].是错误的。

能否求出l的具体值呢?答案是可以的。根据GoCalf[2]GoCalf. 检测单向链表是否存在环. . 2011-10-14 [2015-01-08].,两指针相遇后,快指针暂停慢指针继续走,两指针第二次相遇时,慢指针走的次数就是环长。

求环长

给定任意带环链表,慢指针第二次遇到快指针时走的次数为该带环链表的环长。

求非循环长度

已知环长后,可以求非循环部分的长度a。

获取甲乙两个慢指针,甲先走l次,然后甲乙一起走。因为甲乙步长相同,他们之间始终保持l的差距。当乙第一次进入循环节时,由于甲乙差距为l,l为循环节长度,所以甲跟乙相遇。这时乙所走的步数就是a。

   [ + ]

1. Bluefeather. Share my O(n) complexity and constant space code. Keep the original list. Any comments. . 2014-12-12 [2015-01-08].
2. GoCalf. 检测单向链表是否存在环. . 2011-10-14 [2015-01-08].

“检查链表是否有环,带数学推导”的4个回复

  1. 如果直接求环开始的节点,最后一段的方法就不实用了。
    假设两指针相遇的位置在环首后m处,则快指针走了a+kl+m步,慢指针走了a+tl+m步,a+kl+m=2(a+tl+m),m+a=(k-2t)l,m+a模l余0,所以其实慢指针再走a步就到环首了,就没必要先求环长了。

tanti进行回复 取消回复

电子邮件地址不会被公开。

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)