鏈表三連

一癞季、如何找到兩個鏈表的交點

兩個鏈表有以下3種情況：
（1）相交
$a_1->a_2->……->c_1->c_2->NULL$
$b_1->b_2->……->c_1->c_2->NULL$
（2）平行
$a_1->a_2->……->a_n->NULL$
$b_1->b_2->……->b_n->NULL$
（3）屬于
$a_1->a_2->……->b_1->b_2->NULL$
$b_1->b_2->NULL$
其中鏈表A劫瞳、B長度未知
可以設(shè)鏈表A到相交節(jié)點長度為 $l_a$ ，鏈表B到相交節(jié)點長度為 $l_b$ 绷柒。對于特殊情況（2） $l_a$ 志于， $l_b$ 分別為鏈表A、B長度废睦；對于特殊情況（3） $l_b=0$ 伺绽。
如果將鏈表AB連接，所得到的鏈表AB和鏈表BA長度必然相等嗜湃。
若設(shè)鏈表A奈应、B公共節(jié)點長度為s，公共節(jié)點為C购披，C在AB中出現(xiàn)的位置有 $len（A）+ l_b=l_a+s+l_b$ 杖挣。在BA中出現(xiàn)的位置有 $len（B）+ l_a=l_b+s+l_a$ 。因此刚陡，令指針 $l_1$ 先遍歷A再遍歷B惩妇，指針 $l_2$ 先遍歷B再遍歷A，則兩個指針必定在交點相遇筐乳。

二歌殃、如何判斷鏈表中是否有環(huán)

可以使用快慢指針。假設(shè)B以A兩倍速度繞操場跑步蝙云，那么B最終一定會追上A挺份。判斷有環(huán)也是同理。
假設(shè)鏈表L到環(huán)的起點長度為x贮懈，環(huán)的長度為m匀泊，環(huán)起點為T。
慢指針slow每次前進一步朵你，快指針fast每次前進兩步各聘。則當(dāng)slow到達環(huán)的起點時，fast在環(huán)中前進了x步抡医。距離再次回到T長度為(m-x%m)躲因。
此時，等同于fast落后slow指針(m-x%m)步忌傻。已知fast速度是slow兩倍大脉。可得fast和slow必定在節(jié)點T后(m-x%m)步相遇水孩。
可得镰矿，若快慢指針相遇，則有環(huán)俘种；否則秤标，沒有環(huán)。

三宙刘、找到環(huán)的起始節(jié)點

由二可得苍姜，fast和slow必定在節(jié)點T后(m-x%m)步相遇。
m-x%m=m-(x-nm)=(n+1)m-x
即還差x步可以繞環(huán)走n+1圈悬包。
那么在找到相遇節(jié)點后衙猪，令另一個指針start從起始節(jié)點出發(fā)，與slow指針同步前進布近，走x步后正好與slow指針在環(huán)起始節(jié)點相遇垫释。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市吊输，隨后出現(xiàn)的幾起案子饶号，更是在濱河造成了極大的恐慌，老刑警劉巖季蚂，帶你破解...
沈念sama閱讀 221,198評論 6贊 514
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件茫船，死亡現(xiàn)場離奇詭異，居然都是意外死亡扭屁，警方通過查閱死者的電腦和手機算谈，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,334評論 3贊 398
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來料滥，“玉大人然眼，你說我怎么就攤上這事】梗” “怎么了高每？”我有些...
開封第一講書人閱讀 167,643評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵屿岂，是天一觀的道長。經(jīng)常有香客問我鲸匿，道長爷怀，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 59,495評論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任带欢，我火速辦了婚禮运授，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘。我一直安慰自己，他們只是感情好宁炫，可當(dāng)我...
茶點故事閱讀 68,502評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布啥供。她就那樣靜靜地躺著，像睡著了一般。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,156評論 1贊 308
城市分裂傳說
那天锦溪，我揣著相機與錄音，去河邊找鬼府怯。笑死刻诊，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的牺丙。我是一名探鬼主播则涯，決...
沈念sama閱讀 40,743評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼冲簿！你這毒婦竟也來了粟判？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,659評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤峦剔，失蹤者是張志新（化名）和其女友劉穎档礁，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體吝沫，經(jīng)...
沈念sama閱讀 46,200評論 1贊 319
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡呻澜，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,282評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了惨险。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片羹幸。...
茶點故事閱讀 40,424評論 1贊 352
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖辫愉，靈堂內(nèi)的尸體忽然破棺而出栅受，到底是詐尸還是另有隱情，我是刑警寧澤，帶...
沈念sama閱讀 36,107評論 5贊 349
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布屏镊，位于F島的核電站依疼，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏闸衫。R本人自食惡果不足惜涛贯，卻給世界環(huán)境...
茶點故事閱讀 41,789評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望蔚出。院中可真熱鬧，春花似錦虫腋、人聲如沸骄酗。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,264評論 0贊 23
一樁弒父案悦冀，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽趋翻。三九已至，卻和暖如春盒蟆，著一層夾襖步出監(jiān)牢的瞬間踏烙，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,390評論 1贊 271
情欲美人皮
我被黑心中介騙來泰國打工历等，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留讨惩，地道東北人。一個月前我還...
沈念sama閱讀 48,798評論 3贊 376
代替公主和親
正文我出身青樓寒屯，卻偏偏與公主長得像荐捻，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子寡夹，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,435評論 2贊 359

鏈表三連

一癞季、如何找到兩個鏈表的交點

二歌殃、如何判斷鏈表中是否有環(huán)

三宙刘、找到環(huán)的起始節(jié)點

推薦閱讀更多精彩內(nèi)容