题解 | #链表中环的入口结点#

/* struct ListNode { int val; struct ListNode next; ListNode(int x) : val(x), next(NULL) { } }; / class Solution { public: ListNode EntryNodeOfLoop(ListNode pHead) {

//方法一：自己做的，先判断有无环，若有环，从根节点开始断开前结点pre（pre==NULL），从当前节点tmp遍历是否有环
//若有环，则恢复上一节点pre的连接pre=tmp，并pre=tmp,tmp=tmp->next,再断开前结点pre,从tmp开始遍历
//知道tmp后的链表无环，此时有结点pre就是环形链表的入口
    
    //先判断有无环
    if(pHead==nullptr||pHead->next==nullptr)
        return nullptr;
    
    ListNode* slow=pHead;
    ListNode* fast=pHead->next->next;
    bool check=false;
    
    while(fast&&fast->next)
    {
        if(slow==fast)
        {
            check=true;
            break;
        }
        fast=fast->next->next;
        slow=slow->next;           
        
    }
    if(check==false)       //无环情况下返回nullptr
        return nullptr;
    

    //有环情况下对环入口结点的寻找
    ListNode* pre=pHead;
    ListNode* tmp=pre->next;
    pre->next=nullptr;
    
    while(true)
    {
        slow=tmp;
        if(tmp->next)
        {  
            fast=tmp->next->next;
        }
        else
            return pre;
        
         check=false;
    
        while(fast&&fast->next)
        {
            if(slow==fast)
            {
                check=true;
                break;
             }
            fast=fast->next->next;
            slow=slow->next;           
        
         }
         if(check==false)       //无环情况下返回nullptr
             return pre;
         else
         {
             //回溯
             pre->next=tmp;
             pre=tmp;
             tmp=tmp->next;
             pre->next=nullptr;
             
         }
    }
    
    
    
    /*
    //方法二，利用有环遍历的规律，若fast和slow的相遇点为tmp,则tmp和头结点pHead以相同速度继续向后遍历
    //同等位数，相等时的结点即为入口节点
    
    //先判断链表为空的情况
    if(pHead == NULL)
        return NULL;
    //快慢双指针
    ListNode* fast = pHead;
    ListNode* slow = pHead;
    //如果没环快指针会先到链表尾
    while(fast != NULL && fast->next != NULL)  
    {
        //快指针移动两步
        fast = fast->next->next;
        //慢指针移动一步
        slow = slow->next;
        //相遇则有环
        if(fast == slow)
            //返回相遇的地方
            break;
    }
    
    //没有环
    if(!fast||(!fast->next))
        return nullptr;
    

    //快指针回到表头
    fast = pHead;
    //再次相遇即是环入口
    while(fast != slow){
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
    */
    
}

};