判断链表中的环的入口节点

有一个单向链表，判断链表中是否有环，如果有，返回环的入口节点。

测试用例：

功能测试：链表中包含或者不包含环，链表有多个或者一个节点

特殊值测试：头指针为空

#include<iostream>
#include<string.h>

using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int i=0)
    {
        val=i;
        next=nullptr;
    }
};

ListNode* HasRing(ListNode* head)
{
    if(head==nullptr)
        return head;
    
    ListNode* fast=head->next;
    ListNode* slow=head;
    
    while(fast&&slow)
    {
        if(fast==slow)
            return fast;
        
        slow=slow->next;
        fast=fast->next
        
        if(fast)
            fast=fast->next;
    }
    
    return nullptr;
}

ListNode* FindEntry(ListNode* head)
{
    ListNode* meetnode=HasRing(head);
    if(!head||!meetnode)
        return nullptr;
    
    ListNode* tmp=meetnode;
    tmp=tmp->next;
    int num=1;
    while(tmp!=meetnode)
    {
        num++;
        tmp=tmp->next;
    }
    
    ListNode* pNode1=head;
    while(num--)
        pNode1=pNode1->next;
    
    ListNode* pNode2=head;
    while(pNode1!=pNode2)
    {
        pNode1=pNode1->next;
        pNode2=pNode2->next;
    }
    
    return pNode1;
}

可以分为两步考虑，第一步，判断链表中有没有环，建立两个指针，指针1每次向前走一个节点，指针2每次向前走两个节点，当指针2走到尾节点等于空时，链表中没有环，或者当两个指针相遇时，链表中有环。然后计算出环的节点数目num，让一个指针pNode1从头结点走num个节点，然后pNode2指针从头结点和pNode1一起向前走，当两者相遇则找到环的入口节点。