写在前面

剑指offer：链表中环的入口结点

题目要求

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解法

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(!pHead||pHead->next==nullptr) return nullptr;
        ListNode* fast = pHead, *slow = pHead;
        while(fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast==slow) break;
        }
        if(!fast) return nullptr;
        fast = pHead;
        while(fast!=slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

分析：
首先使用快慢指针，快指针一次走两步，慢指针一次走1步，当二者重合的时候说明有环。如果快指针已经到达nullptr说明无环。
当第一次重合的时候该节点并不一定是环的入口节点。但是此时快指针走过的距离一定是慢指针走过的距离的两倍，稍微画图就可以看出，此时令其中一个指针返回起点，两个指针同时一步一步走当二者再次相遇的节点就是入口节点。