追击问题和Floyd判圈法

追击问题大家都知道,是一个算速度差以及距离差的小学题目

速度差×追及时间=追及路程
路程差÷速度差=追及时间

Floyd判圈算法是一个可以在有限状态机、迭代函数或者链表上判断是否存在环,求出该环的起点与长度的算法
如果有限状态机、迭代函数或者链表上存在环,那么在某个环上以不同速度前进的2个指针必定会在某个时刻相遇。同时显然地,如果从同一个起点(即使这个起点不在某个环上)同时开始以不同速度前进的2个指针最终相遇,那么可以判定存在一个环,且可以求出2者相遇处所在的环的起点与长度

设有两个指针同时从链表起点(即点A处)同时前移,快指针fast每次挪动两格,慢指针slow每次挪动一格

一、证明假如有环,两指针必相遇

虽然看起来仿佛是个这还用证的问题,但还是说一下
因为快指针fast移动速度是慢指针slow的两倍,当慢指针slow从起点A运动到环起点B的时候S_{slow} = \frac{1}{2}S_{fast} = m。这时快指针fast在环内,慢指针slow在环起点,实际追击距离为0\leq m - i·l < l(i为非零整数,l为环长)
快指针fast必能追上慢指针slow并且是在一圈内追上

二、如何求环长

设点C为两指针相遇点
慢指针slow从相遇节点开始继续后移,快指针fast不动,当两指针再次相遇时,慢指针slow移动的距离即为环长l

三、环起点的求法及原理

为了求出环的起点,只要令慢指针slow仍均位于节点C,而令快指针fast返回起点节点A,此时fastslow之间距为环长度l的整数倍。随后,同时让fastslow往前推进,且保持二者的速度相同:fast每前进1步,slow前进1步。持续该过程直至fastslow再一次相遇,设此次相遇时位于同一节点B,则节点B即为从节点A出发所到达的环的第一个节点,即环的一个起点

设其中AB距离为m,BC距离为k,环长为l
S_{slow} = m + a·l + k(a为非负整数)
S_{fast} = m + b·l + k(b为非负整数)

S_{fast} - S_{slow} = S_{slow} = (b-a)·l
由此可知慢指针slow的位移环长l的整数倍
S_{slow} = m + a·l + k = (b-a)·l
m = (b-2a)·l - k = (b-2a-1)·l + (l - k)
起点A到环起点B距离m等于环的整数倍外加一段弧长,每次挪1步,必会在点B相遇

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,937评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,503评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,712评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,668评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,677评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,601评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,975评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,637评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,881评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,387评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,971评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2 342

推荐阅读更多精彩内容

  • 1. 环形链表的判定 问题描述给定一个单链表,判断链表中是否存在环。 解题思路设定两个指针:快指针_fast与慢指...
    孙树冲阅读 572评论 0 2
  • 搞懂单链表常见面试题 Hello 继上次的 搞懂基本排序算法,这个一星期,我总结了,我所学习和思考的单链表基础知识...
    醒着的码者阅读 4,572评论 1 45
  • 2. Add Two Numbers 先初始化两个结点,一个用来做head,一个作为指引node不断向下延续的指针...
    Morphiaaa阅读 914评论 0 0
  • 问题:如何检测一个链表是否有环,如果有,那么如何确定环的起点.要求 : 空间复杂度为O(1), 时间复杂度为O(n...
    SeaRise阅读 4,711评论 2 8
  • 周一,早高峰,槐巷口。 甄欣的电动车停在一边,紧赶紧地去扶一个刚被前面的摩托车撞倒在地的老人。虽然受过无数次的教训...
    语熙阅读 698评论 4 5