在很多面试、笔试题目中,经常会出现一些关于单链表的题目,其中比较常见的主要就是问你如何判断一个单链表是否含有环。这是一个比较简单的问题,但是其实还可以问的更难一些的,比如:如何计算环的长度?如何找出环的起始位置?本文对这三个问题分别进行了分析。

是否含有环

这是一个最常见的问题,答案也是非常简单的,只要设置两个步长分别1和2的指针\(p,q\),同时从head开始遍历整个链表,如果链表中含有环的话,则这两个指针\(p,q\)迟早会相遇;如果不存在环,则\(p,q\)永不相遇。

计算环的长度

这个问题承接于上一个问题,如果存在环的话,那么\(p,q\)相遇的位置一定是在环内部,则此时只需要固定\(p\),让\(q\)以步长1继续往前走,记录其步数,直到再次遇到\(p\),则\(q\)所走步数就是环的长度。

环的起始位置

这个问题同样是承接于第一个问题,这个方法稍微有些复杂,首先说明一个算法过程,然后再证明它。

假设\(p,q\)相遇在\(k\),此时令\(p\)指向head(此时,q指向k,p指向head),然后\(p,q\)分别继续往下遍历(步长为1),当\(p,q\)再次相遇的时候,相遇的节点就是环开始的位置。

证明:

假设链表中环的起始位置为\(S\),head与\(S\)之间有\(\mu\)个节点,环的长度1\(n\)\(p,q\)第一次相遇的位置为\(K\)\(S\)\(K\)之间有\(k\)个节点(\(k\le n\))。假设p的步长为1,q的步长为2,令\(x\)表示\(q\)从head到\(K\)一共经过的节点数2。则:

$$ x=\mu + i\cdot n+k $$

而对于\(p\)来说,因为起步长为1且\(p,q\)是同步运行的,所以\(p\)经过的节点数应该为\(2x\):

$$ 2x=\mu+j\cdot n +k $$

根据上述的等式,解出\(\mu=(j-2i)\cdot n-k\),将其代回\(x\)中,我们可以得到:

$$ x = (j-i)\cdot n \Rightarrow x+\mu = (j-i)\cdot n + \mu $$

上述等式就说明了,当\(p,q\)相遇之后,再按步长为1,向前走\(\mu\)个节点,就可以到达环的起始位置。

\(\Box\)


  1. 也即环中的节点数 

  2. 虽然\(q\)的步长是2,但是计算的经过的节点时,每一个在\(q\)前面的节点都会被计算,不仅仅是其指向的节点。 

Share on: TwitterFacebookEmail


Flyaway is the owner of this blog.

Published

Category

algorithm

Tags

Contact