這是一題常見的面試題，考察求職者對鏈表的理解，題目在leetcode上：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
首先來判斷鏈表有沒有環(huán)?？匆粋€直觀的例子：假設(shè)小明和專業(yè)運動員在400米標(biāo)準(zhǔn)環(huán)形操場上比賽跑步，由于長久缺乏鍛煉，小明勻速跑一圈需要2分鐘，而運動員勻速跑一圈只要1分鐘。那么如果兩個人同時、同一點出發(fā)，1分鐘后小明跑了半圈，而運動員已經(jīng)跑完一圈，開始第二圈；2分鐘時，小明終于跑完一圈，而運動員剛好跑完第二圈，整整比小明多跑一圈，兩人在終點相遇。如果運動員在小明前方S米處和小明同時出發(fā)，那么運動員會在小明跑完一圈前就追上小明（可憐的小明）。

回歸問題，如果我們設(shè)定兩個指針p1、p2，開始時指在鏈表頭head，p1代表小明，每次前進(jìn)一步；p2代表運動員，每次前進(jìn)兩步。如下圖環(huán)形鏈表中，6步之后p2追上p1，再次相遇。

環(huán)鏈表

對于一般鏈表，p1、p2仍然同時從表頭A點出發(fā)，由于前面有段非環(huán)的直線路程，當(dāng)p1到B點進(jìn)入環(huán)的時刻，p2已經(jīng)在環(huán)內(nèi)跑了一段路了，此刻開始，類似運動員和小明同時出發(fā)，而運動員的出發(fā)點領(lǐng)先于小明，在不超過一圈的路程內(nèi)，運動員能夠追上小明，p2也能在一圈以內(nèi)趕上p1，假設(shè)兩指針在C點相遇，此時，p1==p2，利用這個條件，我們可以斷定鏈表有環(huán)。否則，當(dāng)運動員跑到了盡頭，還沒有和小明相遇，說明他們的跑道沒有環(huán)。

一般鏈表

再來看看環(huán)的入口在哪里。我們利用p1、p2在C點相遇的時刻來分析，假設(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;
相遇時，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時，說明p2比p1多跑了一圈，此時，s = l。當(dāng)n > 1時，說明p2比p1多跑了整整(n -1)圈再相遇，考慮s - l為環(huán)長度的(n -1)倍，(n -1)(r + l) + l = s，說明如果一個節(jié)點從A點開始，走s的距離和從C點開始走(n -1)圈再多l的距離剛好又能相遇在B點，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時，說明沒有環(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;
        }
       // 一個從A前進(jìn)，一個從C前進(jìn)
        p2 = head;
        while(p1 != p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }