題目描述
在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)捅膘，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留寻仗，返回鏈表頭指針凡壤。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
解題思路
這個(gè)題包含兩個(gè)子問題亚侠，一個(gè)是判斷鏈表是否有環(huán)，另一個(gè)是如果有環(huán)硝烂，找到環(huán)的入口。
對(duì)于如何判斷鏈表有環(huán)問題串稀，較為基礎(chǔ)：快慢指針。
-
對(duì)于如何找到環(huán)的入口狮杨，這個(gè)地方需要推導(dǎo)一下：
x表示頭結(jié)點(diǎn)到入口結(jié)點(diǎn)的距離，表示入口結(jié)點(diǎn)到fast和slow相遇結(jié)點(diǎn)的距離橄教，z是環(huán)中剩下的長度，即有z+y=L华烟。L表示的是環(huán)的長度持灰。那么當(dāng)快慢指針相遇時(shí)候有：S = x+y 2*S = x+y+nL。即，慢指針走過x+y的結(jié)點(diǎn)绽族，快指針比慢指針多走了n圈衩藤。這里慢指針在環(huán)中也可能多走了幾圈才相遇的吧慢，但是可以不用表示出來赏表。因?yàn)榭熘羔樀膎L表示的就是比慢指針多走的圈數(shù)。舉例：慢指針如果走 x+y+2L瓢剿，快指針走 x+y+4L 那么就可以寫成：慢x+y 快x+y+2L.是等價(jià)的。
消去s间狂，可得，同時(shí)：
忙菠，代入消去y纺弊，可得
如圖
得到 能說明什么問題呢？
走x步傍睹，等于走 n-1圈再走上z步。走x步拾稳，正好就是從頭結(jié)點(diǎn)到環(huán)入口結(jié)點(diǎn)。而z步是從相遇地方已亥，到入口結(jié)點(diǎn)，在加上多少圈震鹉，實(shí)際走的都是從相遇到入口結(jié)點(diǎn)捆姜。舉個(gè)例子，如果n = 1泥技，那么x=z。如果n=2簸呈，那么x=L+z.就是多走一圈到相遇結(jié)點(diǎn)榕订，然后再走z步還是到環(huán)的入口結(jié)點(diǎn)蜕便。
這個(gè)時(shí)候，我們只需要令一個(gè)結(jié)點(diǎn)從頭結(jié)點(diǎn)出發(fā)轿腺，走x步两嘴，另一個(gè)結(jié)點(diǎn)從相遇結(jié)點(diǎn)出發(fā)族壳，走n圈（n=0,1,2,...）再走z步，他們會(huì)同時(shí)到達(dá)環(huán)的入口地方贰您。
題解
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead == null) return null;
if (isLoop(pHead)){
ListNode slow = pHead.next;
ListNode fast = pHead.next.next;
while(slow != fast){
slow = slow.next;
fast = fast.next.next;
}
// 循環(huán)結(jié)束時(shí)候 slow == fast
slow = pHead;
// 一個(gè)從頭開始走 赖歌，一個(gè)從相遇地方開始走，走同樣的步數(shù)
// 因?yàn)?x= z+(n-1)L
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
else return null;
}
public boolean isLoop(ListNode pHead){
if (pHead.next == null) return false;
ListNode slow = pHead;
ListNode fast = pHead;
while (fast != null && fast.next !=null){
slow = slow.next;
fast = fast.next.next;
if (slow == fast){
return true;
}
}
return false;
}
