单链表OJ题——10.环形链表2

单链表OJ题——10.环形链表2

142. 环形链表 II - 力扣（LeetCode）

/*
解题思路：
如果链表存在环，则fast和slow会在环内相遇，定义相遇点到入口点的距离为X,定义环的长度为C,定义头到入口的距离为L,fast在slow进入环之后一圈内追上slow,则会得知：
slow所走的步数为:L + X
fast所走的步数为：L + X +  * C
并且fast所走的步数为slow的两倍，故：
2*(L + X) = L + X +  * C
即： L =  * C - X
所以从相遇点开始slow继续走，让一个指针从头开始走，相遇点即为入口节点
*/

typedef struct Listode ode;
struct Listode *detectCycle(struct Listode *head) {
    	ode* slow = head;
        ode* fast = head;

        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            //走到相遇点
            if(slow == fast)
            {
                // 求环的入口点
                ode* meet = slow;
                ode* start = head;

                while(meet != start)
                {
                    meet = meet->next;
                    start = start->next;
                }

                return meet;
            }
        }

        return ULL;
}