給定單鏈表时甚，檢測(cè)是否有環(huán)泻仙。如果有環(huán)屑那，則求出進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)拱镐。
判斷單向鏈表是否有環(huán)艘款，可以采用快指針與慢指針的方式來(lái)解決。即定義一個(gè)快指針fast和一個(gè)慢指針slow沃琅，使得fast每次跳躍兩個(gè)節(jié)點(diǎn)哗咆，slow每次跳躍一個(gè)節(jié)點(diǎn)。如果鏈表沒(méi)有環(huán)的話益眉，則slow與fast永遠(yuǎn)不會(huì)相遇（這里鏈表至少有兩個(gè)節(jié)點(diǎn)）晌柬；如果有環(huán)，則fast與slow將會(huì)在環(huán)中相遇郭脂。
然后獲取環(huán)的入口點(diǎn)方法如圖所示：
給定兩個(gè)單鏈表（鏈表自身無(wú)環(huán)）年碘，檢測(cè)兩個(gè)鏈表是否有交點(diǎn)，如果有返回第一個(gè)交點(diǎn)朱庆。
檢測(cè)兩個(gè)單鏈表是否有交點(diǎn)是很容易的盛泡，因?yàn)槿绻麅蓚€(gè)鏈表有交點(diǎn)，那么這兩個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)必須相同娱颊，所以只需比較最后一個(gè)節(jié)點(diǎn)即可傲诵。但是這種方案是無(wú)法求出第一個(gè)交點(diǎn)的，所以需要另辟蹊徑箱硕。另外拴竹，判斷是否有交點(diǎn)可以轉(zhuǎn)換成鏈表是否有環(huán)的問(wèn)題。讓一個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)指向第二個(gè)鏈表的頭結(jié)點(diǎn)剧罩，這樣的話栓拜，如果相交，則新的鏈表是存在環(huán)的惠昔，并且交點(diǎn)便是環(huán)的入口點(diǎn)幕与。
給定兩個(gè)單鏈表（不確定是否帶環(huán)），判斷是否有交點(diǎn)
先判斷兩個(gè)鏈表是否帶環(huán)镇防；
i).如果兩個(gè)都不帶環(huán)啦鸣，可以用：判斷兩個(gè)無(wú)環(huán)單鏈表是否有交點(diǎn)。
ii).兩個(gè)都帶環(huán)：找到兩個(gè)入環(huán)點(diǎn)r1,r2来氧，環(huán)1的入環(huán)點(diǎn)為r1诫给，從r1開(kāi)始遍歷一圈，每個(gè)結(jié)點(diǎn)如r2比較
iii).一個(gè)帶環(huán)一個(gè)不帶環(huán)啦扬，則肯定不相交中狂。
給定單鏈表頭結(jié)點(diǎn)，刪除鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
這個(gè)問(wèn)題的關(guān)鍵是需要獲取倒數(shù)第k個(gè)節(jié)點(diǎn)扑毡。如何獲取呢胃榕？這里，需要兩個(gè)指針p和q瞄摊，p指向頭結(jié)點(diǎn)勤晚，q指向距離頭結(jié)點(diǎn)為k的節(jié)點(diǎn)枉层。這樣p和q每次遍歷一個(gè)節(jié)點(diǎn)泉褐，當(dāng)q遍歷到末尾的時(shí)候赐写，p指向的節(jié)點(diǎn)即為倒數(shù)第k個(gè)節(jié)點(diǎn)，然后刪除即可膜赃。
只給定單鏈表中某個(gè)結(jié)點(diǎn)p（并非最后一個(gè)結(jié)點(diǎn)挺邀，即p->next!=NULL）指針，刪除該結(jié)點(diǎn)跳座；
只給定單鏈表中某個(gè)結(jié)點(diǎn)p（非空結(jié)點(diǎn)）端铛，在p前面插入一個(gè)結(jié)點(diǎn)。
上訴兩種方法的原理都是一樣的疲眷。
作者：kidzss
鏈接：http://www.reibang.com/p/c12f90300077
來(lái)源：簡(jiǎn)書(shū)
著作權(quán)歸作者所有禾蚕。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處狂丝。
