Floyd的cycle-detection算法解析(原创)

要解决的问题是：
如何确定一个链表中时候存在环，如果存在的话，环的起点在哪里?

借用这张经典的解析图


Floyd 的算法又叫做龟兔赛跑算法，那么我们就用龟兔赛跑来解释。
我们假设乌龟和兔子的速度是1:2，然后假设乌龟的兔子在赛道的某一点相遇了。(相当于他们直线跑入一个环形赛道，然后在赛道的某一点相遇了)那么因为他们跑得时间是一样的，即他们跑得路程1个是i，另一个是2i。借用上图的表示，我们有如下等式：

1) i = m + p*n + k
2) 2i = m + q*n + k

这里的p和q分别是兔子和乌龟在环里跑得圈数。q>p
解上面的等式去掉i,我们就得到下面这个重要的等式：

 m + k = (q-2p) * n  (等式一)

因此，如果我们能够证明至少有一种k, p, q的值可以使得这个等式成立，我们就证明了这样的m和n的是存在的。(如果环存在，即上面等式成立，m和n的值是确定不可变的，只有k,p,q是可变值。) 进而也就证明了乌龟和兔子的相遇是成立的。

这里我们只要使 k = m*n-m; q-2p = 2m; 也就是说存在k,q,p的确定的值的组合(因为他们都可以用m和n表示)，使得上式成立。

下面我们来解决第二个问题，即环的起点在哪里。
让我们再加一只乌龟进来，叫做乌龟二号。 乌龟二号和乌龟一号有同样的速度。当乌龟二号在链表起点时，乌龟一号和兔子相遇在环内的K处。
现在，当两只乌龟一起走m步时，即乌龟二号到达了环的起点，这时候

乌龟一号走的总路程 = m + p*n + k + m
根据等式一计算m+k得出：
乌龟一号走的总路程 = (q-2p) * n + p*n + m
即

乌龟一号走的总路程 = (q-p)*n + m

 所以当乌龟二号在环起点的时候，乌龟一号走过了(q-n)圈个环，再加上m的路。所以乌龟一和乌龟二第一次相遇的时候的点就是环的起点。

参考http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

评论

发表评论

此博客中的热门博文

Nu förbjuder Kina handel med elfenben

Det har varit världens största marknad för elfenben. Men nu är handeln förbjuden i Kina. 这里曾经是世界上最大的象牙市场。现在中国禁止了交易。 När 2017 tog slut, då tog även handeln med elfenben på världens största marknad slut. Kina följde då efter USA, vars förbud trädde i kraft 2016. Ett beslut som får miljökämpar att jubla. 当2017年过去，世界上最大的象牙市场也结束了。在USA之后，中国在2016年的禁令也开始生效。这一决定让环保主义者欢呼。 – Vi kan inleda 2018 hoppfulla om att elefanter kommer att vara säkrare nu när Kina har förbjudit kommersiell elfenbenshandel, säger miljöorganisationen WildAid:s ordförande Peter Knights till Huffington Post. 我们可以开始2018希望大象变得更安全，当中国金子了大象的商业交易， 环保组织P被HP采访时说。 Nu hoppas många att förbudet ska få tjuvjakten på elefanter att minska. Enligt WWFpekar rapporter på att det dödas så många som 20 000 afrikanska elefanter varje år. 许多人希望禁令可以使大象盗猎减少。根据WWF的报告每年死亡的非洲大象多大20000头。
阅读全文

Fader av pingyins

Zhou Youguang, född 13 januari 1906 i Changzhou i Jiangsu, död 13 januari 2017 i Peking, var en kinesisk sinolog och lingvist som var ledande i utvecklingen av skriftsystemet pinyin. Han har kallats för pinyins fader. 周有光，出生于1906年1月13日的江苏常州，于2017年1月13日在北京逝世，是中国汉学家和语言学家，在书写系统拼音发展的领导者。他被称为拼音之父。 Zhou Youguang arbetade på en bank i New York innan han återvände till Kina efter det kommunistiska maktövertagandet 1949. Där undervisade han under ett antal år i ekonomi på Fudanuniversitetet i Shanghai. År 1955 anlitades han av Zhou Enlai för att konstruera ett stavningssystem, som skulle komplettera det bildbaserade skriftspråket och ersätta det tidigare transkriberingssystemet Wade–Giles. Detta arbete tog honom ungefär tre år. 之前周有光在在纽约一家银行工作，在1949年共产党收复权利之后回到中国。在那里他在上海的复旦大学教授了许多年的经济学。1955年他被周恩来聘请来建立一套书写系统，能够补充基于图像的书写语言，并且取代早先的Wade－Giles转录系统。这项工作大概花了他三年的时间。
阅读全文

Kineserna vill köpa Volvos kompetens

Det kinesiska bilföretaget Geely äger redan Volvo Cars som tillverkar Volvos personbilar. 中国汽车公司吉利已经拥有生产沃尔沃乘用车的沃尔沃汽车公司。 Nu blir bolaget också storägare i AB Volvo, som bland annat bygger lastbilar och anläggningsmaskiner. 现在该公司也成为沃尔沃AB公司的大股东，沃尔沃AB公司生产卡车和工程机械。 I går meddelade Christer Gardell att hans riskkapitalbolag Cevian säljer hela sitt innehav till det kinesiska bolaget. 昨天Cevian风险投资公司的CG宣布其所有股权卖给中国公司。 Geely blir i ett slag en av AB Volvos största ägare. 吉利一下子变成AB Volvo的最大拥有者。 Möjligen ska jätteaffären ses som ett tecken på att cirkeln är på väg att slutas. 可能这家巨型公司将打破这个轮回。 En av de nya ägarnas förtjänster sägs vara Geelys kompetens när det gäller elektrifiering och självkörande bilar. 据说新东家吉利在电子化和自动驾驶汽车方面有专长。 Kompetensen finns Mycket av den kompetensen finns hos Volvo Cars, som AB Volvo sålde 1999. I bästa fall kan ett delvis gemensamt ägande bidra till att stärka båda Volvos delar. 1999年售出的ABVolvo拥有许多专业知识。一个共同拥有者最多能够强化沃尔沃的一部分。 För Volvo Cars ha...
阅读全文