链表判环

如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的地址，无环的话返回空。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。

策略

1. 定义fast和slow指针；

   
   
2. 前者一次走两步，后者一次走一步；走完之后做一次结算：

• 如果前者越界，说明无环
• 如果两者相遇，说明有环

3. 若相遇，slow回到头结点，开始继续走。但这次fast和slow每次均走一步。

   
   
   
   

4. 两者相遇点即为入环结点。

   
   

CODE

    ListNode* chkLoop(ListNode* head) {
        if(!head || !head->next)
            return nullptr;
        ListNode* H=new ListNode(0);
        H->next=head;
        ListNode *fast=H,*slow=H;
        while(fast->next && fast->next->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                break;
            }
        }
        if(fast!=slow)
            return nullptr;
        slow=H;
        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        delete H;
        return fast;
    }

简略证明

设链表非环内结点数目是m1
环内结点数目是m2
(本例子中，m1=3 m2=6)
慢指针在第n步会到达n结点
快指针在第n步会到达

• 2n (2n<=m1)
• m1+(2n-m1)%m2 (2n>m1)

如果两者第一次相等，则快指针到达 m1+[(2n-m1)-m2]=2n-m2
联立求得 n=m2
也就是说，第一次相遇时的地点是m2号结点。因为链表前段有m1个非环结点，所以m2号结点如果想走到入环点，需要走：m2-(m2-m1)=m1步
此时如果慢指针从头开始走，也需要走m1步
所以两者会相遇在入环点。