【剑指 offer】链表中环的入口。

1、题目描述

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

样例

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

2、问题描述：

• 带环链表，环的入口结点。

3、问题关键：

• 如果有环会存在这样的关系。快慢指针，一个一次走两步，一个一次走一步，肯定会相遇的。
• 如果相遇之后，让一个结点从头结点开始走，再次相遇的时候，就是环的入口。这可以证明，这里先记住这个。

解释：为什么相遇后，一个从头结点开始，再次相遇就是环的入口！！！

解释1：a是起点，b是环的入口点，c是第一相遇的地方，first一次走1步， second一次走两步，second的路程是first的2倍，当first走到c的时候路程为（x + y），second的路程为（x + y）+ n(y + z)圈，2(x + y) = x + y + n,可以得到，x = (n - 1)*(y + z) + z。说明，从c再走x步，刚好到b。

解释2:从2(x + y) = x + y + n圈。x + y = n圈，且n圈的起点是b，所以到c走了y，再走x，那么就又是n圈，回到了起点b。

4、C++代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if (!head || !head->next) return 0;//空结点，或者只有一个结点，那么返回NULL就可以了。
        auto first = head, second = head;
        while(first && second) {
            first = first->next;
            second = second->next;
            if (second) second = second->next;//快指针走两步。
            else return 0;
            if (first == second) {//如果相遇了说明有环。
                first = head;//一个从头开始两个每次走一步，再次相遇就是环的入口。
                while(first != second) {
                    first = first->next;
                    second = second->next;
                }
                return first;
            }
        }
        return 0;
    }
};