IT工程師數位筆記本

題目描述
一個鏈表中包含環，請找出該鏈表的環的入口結點。

初步想法是每個節點做幾個標記，表示是否被訪問過，那么遍歷鏈表的時候就知道哪個被訪問到了。但是不會實現。

另一個直覺是判斷鏈表有環的算法中出現過的策略，分別按1x和2x速度遍歷，總會相遇。假設環長為n。
容易知道，當1x的指針p1和2x的指針p2相遇時，p1走了x步，p2走了2x步，而p2比p1多走的，有兩部分：(1)環內部，p1還沒有走過的；（2）換內部，p1和p2重合的
這兩部分加起來就是整個環。那么其實p2比p1多走的就是這么一個環的距離，也就是說：

2x-x = n  ==> n=x

即：p1當前走了一個環長度的距離。

下圖表示了p1和p2相遇在B點的情況，其中A點開始順時針方向回到A的軌跡就是環形，長度為n。

不妨假設鏈表總長為L，那么：
CA+A環=CA+n=L ==>L-n=CA
CB=x=n=A環
==> BA弧=L-CB=L-n=CA

也即：BA弧=CA，那么指針p1從B繼續走，而指針p2從鏈表起點C從新開始（但是步長這次取1），則當p2到達A點時，p1也到達A點。
對應到算法中，當1x和2x套圈時，p1和p2按照這個策略繼續做while循環，直到再次相遇，就找到了環的入口。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==NULL){
            return NULL;
        }
        if(pHead->next==NULL){
            return NULL;
        }
        ListNode* p1=pHead;
        ListNode* p2=pHead;
        while(p2!=NULL && p2->next!=NULL){
            p1=p1->next;
            p2=p2->next->next;
            if(p1==p2){
                p1 = pHead;
                while(p1!=p2){
                    p1=p1->next;
                    p2=p2->next;
                }
                if(p1==p2){
                    return p1;
                }
            }
        }
        return NULL;
    }
};