- 《程序員面試金典》p49,2.6, 求單鏈表環(huán)路的入口結(jié)點(diǎn)。
- 相關(guān)題目：給定兩個(gè)單鏈表涛碑，求他們的共同交點(diǎn)壁袄。
解法：
（1）利用棧，空間復(fù)雜度高
（2）先對(duì)兩個(gè)鏈表分別作就地反轉(zhuǎn)豆混，然后再一次判斷
（3）先分別遍歷兩個(gè)鏈表篓像，如果能遍歷到相同的尾結(jié)點(diǎn)动知，則兩個(gè)鏈表相交皿伺，同時(shí)記錄下兩條鏈表的長度longlength和shortlength，然后用兩個(gè)指針fast和slow盒粮；fast先走(longlength-shortlength)步鸵鸥，然后他們?cè)偻瑫r(shí)走，到相同時(shí)就是第一個(gè)相交結(jié)點(diǎn)
（4）將兩個(gè)鏈表首尾相連，然后轉(zhuǎn)換為“求單鏈表中環(huán)路的開頭結(jié)點(diǎn)”的問題妒穴。時(shí)間復(fù)雜度O(M+N) - 給定單鏈表頭結(jié)點(diǎn)宋税，刪除鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
分析：這道題可轉(zhuǎn)換為查找鏈表中倒數(shù)第k+1個(gè)結(jié)點(diǎn)；只需要注意k+1和鏈表的長度讼油，注意其中的錯(cuò)誤檢查即可
經(jīng)典面試題之鏈表
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門含友，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人校辩，你說我怎么就攤上這事窘问。” “怎么了召川？”我有些...
- 文/不壞的土叔 我叫張陵南缓，是天一觀的道長。 經(jīng)常有香客問我荧呐，道長汉形，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任倍阐，我火速辦了婚禮概疆，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘峰搪。我一直安慰自己岔冀，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布概耻。 她就那樣靜靜地躺著使套，像睡著了一般。 火紅的嫁衣襯著肌膚如雪鞠柄。 梳的紋絲不亂的頭發(fā)上侦高，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼咆槽！你這毒婦竟也來了陈轿？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬榮一對(duì)情侶失蹤秦忿，失蹤者是張志新（化名）和其女友劉穎济欢，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體小渊，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡法褥，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了酬屉。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片半等。...
- 正文 年R本政府宣布切距，位于F島的核電站，受9級(jí)特大地震影響惨远，放射性物質(zhì)發(fā)生泄漏谜悟。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一北秽、第九天 我趴在偏房一處隱蔽的房頂上張望葡幸。 院中可真熱鬧，春花似錦贺氓、人聲如沸蔚叨。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽蔑水。三九已至，卻和暖如春扬蕊，著一層夾襖步出監(jiān)牢的瞬間搀别，已是汗流浹背。 一陣腳步聲響...
- 正文 我出身青樓蛮穿，卻偏偏與公主長得像庶骄，于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子践磅，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 轉(zhuǎn)載請(qǐng)注明出處：http://www.reibang.com/p/c65d9d753c31 在上一篇博客《數(shù)據(jù)結(jié)構(gòu)...
- 前言 本文是題主準(zhǔn)備面試時(shí)記錄下的筆記整理而來府适，稍顯粗陋羔飞，還請(qǐng)各位擼友勿噴哈！ Topic 目錄數(shù)組字符串鏈表二叉...
- 1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表 題目： 輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表疟暖。 要求不...
- 【聲明】歡迎轉(zhuǎn)載卡儒，但請(qǐng)保留文章原始出處→_→文章來源：http://www.reibang.com/p/08d08...
