题目描述

一个链表中包含环，请找出该链表的环的入口结点。

初步想法是每个节点做几个标记，表示是否被访问过，那么遍历链表的时候就知道哪个被访问到了。但是不会实现。

另一个直觉是判断链表有环的算法中出现过的策略，分别按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;

    }

};