這是一題常見的面試題，考察求職者對鏈表的理解勺爱，題目在leetcode上：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
首先來判斷鏈表有沒有環(huán)晃琳。看一個(gè)直觀的例子：假設(shè)小明和專業(yè)運(yùn)動(dòng)員在400米標(biāo)準(zhǔn)環(huán)形操場上比賽跑步琐鲁，由于長久缺乏鍛煉卫旱，小明勻速跑一圈需要2分鐘，而運(yùn)動(dòng)員勻速跑一圈只要1分鐘围段。那么如果兩個(gè)人同時(shí)顾翼、同一點(diǎn)出發(fā)，1分鐘后小明跑了半圈奈泪，而運(yùn)動(dòng)員已經(jīng)跑完一圈适贸，開始第二圈灸芳；2分鐘時(shí)，小明終于跑完一圈拜姿，而運(yùn)動(dòng)員剛好跑完第二圈烙样，整整比小明多跑一圈，兩人在終點(diǎn)相遇蕊肥。如果運(yùn)動(dòng)員在小明前方S米處和小明同時(shí)出發(fā)谒获，那么運(yùn)動(dòng)員會(huì)在小明跑完一圈前就追上小明（可憐的小明）。
回歸問題壁却，如果我們設(shè)定兩個(gè)指針p1批狱、p2，開始時(shí)指在鏈表頭head展东，p1代表小明赔硫，每次前進(jìn)一步；p2代表運(yùn)動(dòng)員盐肃，每次前進(jìn)兩步爪膊。如下圖環(huán)形鏈表中，6步之后p2追上p1恼蓬，再次相遇惊完。
對于一般鏈表，p1处硬、p2仍然同時(shí)從表頭A點(diǎn)出發(fā)小槐，由于前面有段非環(huán)的直線路程，當(dāng)p1到B點(diǎn)進(jìn)入環(huán)的時(shí)刻荷辕，p2已經(jīng)在環(huán)內(nèi)跑了一段路了凿跳，此刻開始，類似運(yùn)動(dòng)員和小明同時(shí)出發(fā)疮方，而運(yùn)動(dòng)員的出發(fā)點(diǎn)領(lǐng)先于小明控嗜，在不超過一圈的路程內(nèi)，運(yùn)動(dòng)員能夠追上小明骡显，p2也能在一圈以內(nèi)趕上p1疆栏，假設(shè)兩指針在C點(diǎn)相遇，此時(shí)惫谤，p1==p2壁顶，利用這個(gè)條件，我們可以斷定鏈表有環(huán)溜歪。否則若专，當(dāng)運(yùn)動(dòng)員跑到了盡頭，還沒有和小明相遇蝴猪，說明他們的跑道沒有環(huán)调衰。
再來看看環(huán)的入口在哪里膊爪。我們利用p1、p2在C點(diǎn)相遇的時(shí)刻來分析嚎莉，假設(shè)AB的距離為s米酬，BC的距離為r，CB的距離為l趋箩，p1走過距離為a = s + r則可以有以下關(guān)系：
(1)總長度 = s + r + l;
(2)環(huán)的長度 = r + l;
(3)p2走過距離 = 2a;
(4)p2 - p1 = a = s + r;
相遇時(shí)淮逻，p2比p1在環(huán)內(nèi)多走了n圈(n>=1):
(5) p2 - p1 = n(r + l)；
結(jié)合(4)阁簸、(5): n(r + l) = s + r;
nr - r = s - nl;
(n - 1)r = s - (n - 1)l -l;
(6) (n -1)(r + l) = s - l;
從（6）我們可以看出一些規(guī)律（注意：環(huán)的長度 = r + l），當(dāng)n = 1時(shí)哼丈，說明p2比p1多跑了一圈启妹，此時(shí)，s = l醉旦。當(dāng)n > 1時(shí)饶米，說明p2比p1多跑了整整(n -1)圈再相遇，考慮s - l為環(huán)長度的(n -1)倍车胡，(n -1)(r + l) + l = s檬输，說明如果一個(gè)節(jié)點(diǎn)從A點(diǎn)開始，走s的距離和從C點(diǎn)開始走(n -1)圈再多l的距離剛好又能相遇在B點(diǎn)匈棘，B也正是環(huán)的入口丧慈。
分析完畢，再上C++代碼：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *detectCycle(ListNode *head) {
ListNode *p1 = head, *p2 = head;
bool hasCycle = false;
// 特殊情況判斷
if(head == NULL)
return NULL;
// p2走得快主卫，當(dāng)p2->next == NULL時(shí)逃默，說明沒有環(huán)
while(p2 && p2->next)
{
p1 = p1->next;
p2 = p2->next->next;
if(p1 == p2)
{
// 有環(huán)，立下flag
hasCycle = true;
break;
}
}
if(!hasCycle)
{
return NULL;
}
// 一個(gè)從A前進(jìn)簇搅，一個(gè)從C前進(jìn)
p2 = head;
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
