判断链表中环的入口节点

判断链表中环的入口节点

要求

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。 这个问题比较绕，原因是这是个数学循环问题，我们这里来做一个证明。假设链表全长为 m+n，其中 m 表示环入口之前的长度，n 表示环的长度，当两指针第一次相遇，这时候快指针一定已经饶了环一圈了，我们假设相遇的位置距离环入口k，此时有下列状态： distance(fast) = m + n + k distance(slow) = m + k 因为fast要比slow快2倍，所以有m + n + k =2（ m + k ） 于是化简有n=m+k 我们已经知道了环的长度是n，此时slow在环里走了k，还剩下m步就回到入口处，所以让一个指向头指针的b和slow开始一步一步移动，最终它们走了m步后会在入口处相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
          
   
    struct ListNode *p,*q,*b;      //双指针来了！！
    int j=0;
    p=head;                       //初始化
    q=head;
    b=head;
    while(q!=NULL&&q->next!=NULL)   //判断是有环
    {
          
   
        p=p->next;       
        q=q->next->next;
        if(p==q)     //有环！！！
        {
          
   
            while(b!=p)      //根据上面的分析，让slow和b一起一步一步走，当相遇，说明是入口节点。
            {
          
   
                b=b->next;
                p=p->next;
            }
            return b;       //返回b指针
        }
    }
    return NULL;      //没有环返回NULL
}