寻找链表中的环的入口（C语言）

声明：题目来源：力扣（LeetCode）

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL 。

题目链接：环形链表II

说明：不允许修改给定的链表。
示例可参考博客：判断链表中是否有环，解法与该题类似，需要先判断是否有环，若有环才能进行寻找入环节点的步骤，否则就直接返回NULL了。
那如何寻找入环节点呢，方法也不复杂，与第4题类似。在判断出链表有环之后，计算出环的长度，再设置快慢两个指针，快指针先走一个环的长度，慢指针再和快指针同时走，两者相遇的位置即为环的入口。
参考代码如下：

struct ListNode *detectCycle(struct ListNode *head) {
    if(head == NULL){
        return NULL;
    }
    struct ListNode *pre = head;
    struct ListNode *lag = head;
    while(pre){
        lag = lag->next;
        pre = pre->next;            
        if(pre){
            pre = pre->next;
        }       
        if(lag == pre){
            break;
        }
    }
    if(pre == NULL){
        return NULL;
    }
    struct ListNode *pre2 = head;
    do{
        pre2 = pre2->next;
        lag = lag->next;
        pre = pre->next;            
        pre = pre->next;        
    }while(lag != pre);
    lag = head;
    while(pre2 != lag){
        lag = lag->next;
        pre2 = pre2->next;
    }
    return lag;
}

上面的代码是正常人写的，但是这种方法还可以优化，不过需要我们使用数学方法来推导。

如图，假设入环前的节点有 L1 个，相遇点距入口有 L2 个，环有 N 个节点，fp 在环内走了 k1 圈，sp 在环内走了 k2 圈，那么 fp 与 sp 相遇时两者走过的路劲长度应满足：

消去 fp、sp 的路程，解出：

L1 + L2 = kN，k为正整数

也就是说，若有指针从表头出发，它走到入口时，相当于走了kN - L2的长度，这个长度，刚好也可以使 fp 或 sp 从相遇的位置走到入口。
于是求环长度的步骤可以省略，当 fp 与 sp 相遇时，使一个指针从表头出发，另一个指针也同时与之从 fp、sp 相遇点出发，这两个指针相遇时的节点，即为环的入口节点。

以下是学数学的人写的代码：

struct ListNode *detectCycle(struct ListNode *head) {
    if(head == NULL){
        return NULL;
    }
    struct ListNode *pre = head;
    struct ListNode *lag = head;
    while(pre){
        lag = lag->next;
        pre = pre->next;            
        if(pre){
            pre = pre->next;
        }
        if(lag == pre){
            break;
        }       
    }
    if(pre == NULL){
        return NULL;
    }
    lag = head;
    while(pre != lag){
        lag = lag->next;
        pre = pre->next;
    }
    return lag;
}