給定單鏈表，檢測是否有環(huán)。如果有環(huán)，則求出進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)。

判斷單向鏈表是否有環(huán)，可以采用快指針與慢指針的方式來解決。即定義一個(gè)快指針fast和一個(gè)慢指針slow，使得fast每次跳躍兩個(gè)節(jié)點(diǎn)，slow每次跳躍一個(gè)節(jié)點(diǎn)。如果鏈表沒有環(huán)的話，則slow與fast永遠(yuǎn)不會相遇（這里鏈表至少有兩個(gè)節(jié)點(diǎn)）；如果有環(huán)，則fast與slow將會在環(huán)中相遇。
然后獲取環(huán)的入口點(diǎn)方法如圖所示：

給定兩個(gè)單鏈表（鏈表自身無環(huán)），檢測兩個(gè)鏈表是否有交點(diǎn)，如果有返回第一個(gè)交點(diǎn)。

檢測兩個(gè)單鏈表是否有交點(diǎn)是很容易的，因?yàn)槿绻麅蓚€(gè)鏈表有交點(diǎn)，那么這兩個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)必須相同，所以只需比較最后一個(gè)節(jié)點(diǎn)即可。但是這種方案是無法求出第一個(gè)交點(diǎn)的，所以需要另辟蹊徑。另外，判斷是否有交點(diǎn)可以轉(zhuǎn)換成鏈表是否有環(huá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è)無環(huán)單鏈表是否有交點(diǎn)。
　　ii).兩個(gè)都帶環(huán)：找到兩個(gè)入環(huán)點(diǎn)r1,r2，環(huán)1的入環(huán)點(diǎn)為r1，從r1開始遍歷一圈，每個(gè)結(jié)點(diǎn)如r2比較
　 iii).一個(gè)帶環(huán)一個(gè)不帶環(huán)，則肯定不相交。

給定單鏈表頭結(jié)點(diǎn)，刪除鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)

這個(gè)問題的關(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)。

上訴兩種方法的原理都是一樣的。