题目描述

判断单链表中是否存在环，如果存在就输出环的入口结点，否则输出NULL

思路：

1. 设置两个快慢指针，快的每次走两步，慢的每次走一步
2. 如果存在环，那么快慢指针一定会相遇
3. 相遇的时候，就重新设置一个指针，指回初始结点，然后慢指针不动
4. 接下来两者每次都走一步，当两者相遇时，就是环的入口结点

PS：对于这道题，表面上是链表的题，其实是一道数学的证明题，读者可以再网上搜索本题的证明。

C代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode LNode;
struct ListNode *entryNodeOfLoop(struct ListNode *head) {
    LNode *fast = head,*slow = head;//设置两个快慢指针
    while(fast&& fast->next){
        slow = slow->next;//慢指针每次走一步
        if(!fast->next) return NULL;
        fast = fast->next->next;//快指针每次走两步
        if(fast == slow){//如果快慢指针相遇，表明存在环
            LNode *p1 = head;//此时就让一个指针重新回到初始位置
            while(p1 != slow){//之后这两个指针同时移动(每次都走一步)，当他们相遇时，就是环入口结点
                p1 = p1->next;
                slow = slow->next;
            }
            return p1;//返回入口结点
        }
    }
    return NULL;
}