《劍指offer》面試題23：鏈表中環(huán)的入口節(jié)點
題目：給一個鏈表，若其中包含環(huán)，請找出該鏈表的環(huán)的入口結點哮翘，否則，輸出null毛秘。
思路：
原書中給出的思路：解決問題的第一步是如何確定一個鏈表有環(huán)饭寺。我們可以用兩個指針來解決這個問題。定義兩個指針叫挟，同時從鏈表的頭節(jié)點出發(fā)艰匙，一個指針一次走一步，另一個指針一次走兩步抹恳。如果走的快的指針追上了走得慢的指針员凝，那么鏈表就包含環(huán)；如果走的快的指針走到了鏈表的末尾都沒有追上第一個指針奋献，那么鏈表就不包含環(huán)健霹。
第二步是如何找到環(huán)的入口。我們還是用兩個指針來解決這個問題瓶蚂。先定義兩個指針p1和p2指向鏈表的頭節(jié)點骤公。如果鏈表的環(huán)中有n個節(jié)點，則指針p1先在鏈表上向前移動n步扬跋，然后兩個指針以相同的速度向前移動阶捆。當?shù)诙€指針指向環(huán)的入口節(jié)點時，第一個指針已經圍繞著環(huán)走了一圈钦听，又回到了入口節(jié)點洒试。
剩下的問題是如何得到環(huán)中節(jié)點的數(shù)目。我們在前面提到判斷一個鏈表里是否有環(huán)時用到了一快一慢兩個指針朴上，如果兩個指針相遇垒棋，則表明鏈表中有環(huán)。兩個指針相遇的節(jié)點一定是在環(huán)中痪宰〉鸺埽可以從這個節(jié)點出發(fā)，一邊繼續(xù)向前移動一邊計數(shù)衣撬，當再次回到這個節(jié)點時乖订，就可以得到環(huán)中節(jié)點數(shù)了。
可以進行優(yōu)化的地方：如何得到環(huán)中節(jié)點的數(shù)目n具练？在判斷鏈表是否有環(huán)時用到了一快一慢兩個指針乍构，如果它們相遇，則表明鏈表中有環(huán)扛点。相遇時走的快的指針走的步數(shù)剛好比走的慢的指針走的步數(shù)多n步哥遮。這相當于運動學上的追擊問題岂丘，追上的條件是剛好多走“一圈”，在這里可以在兩個指針走的過程中對指針走的步數(shù)分別進行計數(shù)眠饮，當它們相遇時奥帘，計數(shù)之差就是環(huán)中節(jié)點的數(shù)目。對比書中給出的解法：不用在得到相遇節(jié)點之后再走n步得到n仪召。減少了常量級別的時間復雜度寨蹋。
勘誤：之前認為在求環(huán)中節(jié)點數(shù)目ｎ時可以利用運動學中的追擊問題的特性進行時間復雜度上的優(yōu)化，但在與同學的討論中發(fā)現(xiàn)之前的思路是錯誤的返咱，之前認為在判斷鏈表是否有環(huán)時用到的一快一慢兩個指針相遇的條件是快指針剛好多走"一圈"钥庇，但實際上是多走了n圈，之前在思考的過程中將兩個指針想象成兩個人在操場跑步進行追擊咖摹，人跑步的相遇條件確實是"一圈"评姨，但兩個指針一快一慢的"走"，"擦肩而過"并不叫相遇萤晴，只有當兩個指針指向同一節(jié)點時才是真的相遇吐句。
代碼如下：
public ListNode EntryNodeOfLoop(ListNode head) {
// 得到相遇節(jié)點
ListNode meetingNode = getMeetingNode(head);
if (meetingNode == null) {
return null;
}
// 計算環(huán)中節(jié)點總數(shù)
int count = 1;
ListNode node1= meetingNode.next;
while (node1 != meetingNode) {
node1 = node1.next;
count++;
}
// 讓node1指針先走count步，node2再與node1一起走
node1 = head;
ListNode node2 = head;
for (int i = 0;i < count;i++) {
node1 = node1.next;
}
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
}
// 相遇點即為環(huán)的入口節(jié)點
return node1;
}
private ListNode getMeetingNode(ListNode head) {
ListNode node1 = head;
ListNode node2 = head;
while (node1.next != null && node2.next != null) {
node1 = node1.next;
node2 = node2.next.next;
if (node1 == node2) {
return node1;
}
}
return null;
}
