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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
 bool hasCycle(ListNode *head) {
        bool ifhascycle=false;
        if(head == nullptr|| head->next==nullptr)
        {
            return false;
        }
        if(head->next==head)
        {
            return true;
        }
        ListNode* p1=head;
        ListNode* p2=head;
        int i=1;
       while(p1->next!=nullptr&&p2->next!=nullptr)
       {
            if(i%2==0)
            {
                p1=p1->next;
            }
            p2=p2->next;
            if(p2==p1)
            {
                ifhascycle=true;
                break;
            }
            i++;
       }
        return ifhascycle;
    }

    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead==nullptr)
        {
            return nullptr;
        }
         bool ifcycle=hasCycle(pHead);
         bool wcycle=true;
         ListNode* p1=pHead;
         ListNode* p2=pHead->next;
         if(!ifcycle)
         {
            return nullptr;
         }
         else {
            while(wcycle)
            {
                p1->next=nullptr;
               wcycle=hasCycle(p2);
               p1->next=p2;
               if(wcycle)
               {
                p1=p2;
               p2=p2->next;
               }
            }
            return p1;
            
         }
         
    }
};

设置两个指针，分别是当前和下一个，断开当前与下一个的链接，判断以下一个为头结点的链表是否存在环，不管是否存在环，判断完成一定要链接上当前与下一个。如果存在环，当前和下一个分别右移一个，继续判断；如果不存在环，那么此时的p1就是环的开头，所以在while循环里不需要对p1和p2进行右移，循环结束以后，直接返回p1即可。