チェーンテーブル内のリングのエントリノードを判断する

チェーンテーブルにリングがあるかどうかを判断する一方向チェーンテーブルがあり、ある場合はリングの入口ノードに戻ります.

テスト例：

機能テスト:チェーンテーブルにリングが含まれているか、含まれていないか、チェーンテーブルに複数のノードがあるか
特殊値テスト:ヘッドポインタが空です

#include
#include

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;
}

2つのステップに分けて考えることができ、第1のステップは、チェーンテーブルにリングがあるかどうかを判断し、2つのポインタを確立し、ポインタ1が1つのノードを前に進むたびに、ポインタ2が2つのノードを前に進むたびに、ポインタ2がエンドノードに等しくなると、チェーンテーブルにリングがないか、または2つのポインタが出会ったときにチェーンテーブルにリングがある.次に、ループのノード数numを算出し、1つのポインタpNode 1をnum個のノードから先頭ノードに移動させ、pNode 2ポインタを先頭ノードとpNode 1とともに前進させ、両者が出会うとループの入口ノードを見つける.