链表中环的入口结点-算法题0002

题目

  牛客网上的题，题目链接: link牛客网上的解答已经很nice了，但是我相信一定有很多大兄弟、小姐妹不理解快那个式子咋推的。作为一名机械狗，来我班门弄个fu。

图解

  虽然是道链表题，但是先要转换到物理场景。题目是：求等量关系，程序员的速度是2单位/秒，老爷爷的速度是1单位/秒，从起点出发走一段直线，接着绕操场跑圈。很容易想明白的是，程序员肯定会反超一圈追上老爷爷，假设向下的箭头所指的位置是程序员反超老爷爷一圈并刚刚相遇的位置。

问：程序员以2单位/s的速度从箭头位置出发，老爷爷从左侧起点位置出发，他们会在哪相遇？

因为是同时出发，所以经过相同的时间程序员走的路途是老爷爷的2倍，得出下面这个式子：
2（A+B）=A + N（B+C）+B················································（公式 1）
这个式子就是老爷爷走到相遇点时走的路径是A+B，程序员走的路径应是2*（A+B），也是A + N（B+C）+B，N是指可能绕圈跑了N圈，这个也不难理解，假设直线跑道超级长，圈又比较小，则老爷爷从家跑到操场的时候，程序员在小圈子里绕了N圈。

我们对公式1做下调整得公式2

2（A+B）=A + （N-1)(B+C)+B+B+C················································（公式 2）
化解得：
A = (N-1)(B+C) + C·······································································（公式 3）
如何理解公式3呢？这是关键，图中很容易看出B+C是一圈， (N-1)(B+C)就是N-1圈。操场跑道不变，我们换个起点，两个老爷爷，一个从起点出发，一个从图中的相遇点（向下的箭头那），当从起点出发的程序员走到操场的入口节点的时候，另一个程序员从相遇点绕圈N-1圈，又走了C距离，在操场的入口处相遇！！！理解的时候把公式3理解为：A = (N-1)(C+B) + C,仅仅是换了下位置就好理解的多了。

代码

  我们先把上面的思想理解了，接受了。再写代码就行云流水了。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        auto pFast = pHead;
        auto pSlow = pHead;
        while(pFast)
        {
            if(pFast->next)
            {
                pFast = pFast->next->next;//走两步
                pSlow=pSlow->next;
            }
            else
            {//单节点自己指向自己进不了这个逻辑分支
                return NULL;//不存在环
            }
            if(pFast == pSlow)//第一次相遇
            {
                pSlow = pHead;
                break;
            }           
        }
        //如果pSlow== pHead 说明相遇了  实际能执行到这肯定是满足这个条件了
        if(pSlow == pHead)
        {
            while(pSlow!=pFast)
            {
                pSlow = pSlow->next;
                pFast = pFast->next;
            }
            return pSlow;
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45