环形链表问题2（返回链表开始入环的第一个节点）

环形链表问题2（返回链表开始入环的第一个节点）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/linked-list-cycle-ii/description/

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

如果链表中有某个节点，可以通过连续跟踪?next?指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数?pos?来表示链表尾连接到链表中的位置（索引从 0 开始）。如果?pos?是?-1，则在该链表中没有环。注意：pos?不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改?链表。

结论：：

一个指针从相遇点开始走，一个指针从头走，那么他们会在入口点相遇。

证明：

?更加严谨的推理过程为:

fast:

L+N*c+x

slow:

L+x

L+N*c+x=2（L+x）

N*c=L+x;

N*c-x=L

(N-1)c+c-x=L

(N-1)c指的是还的周长很小的时候，一个指针从相遇点出发走c-x,与一个指针从头走l，最终可以在环的入口点相遇。

代码：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow=NULL,*fast=NULL;
    slow=fast=head;
    while(fast&&fast->next){
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast){
         struct ListNode *met=slow; 
         while(met!=head){
             met=met->next;
             head=head->next;
         }
            //return true;
            return met;
        }
    }
    return false;
}

?