leetcode:チェーンテーブルのリングの入口ノード


タイトル://チェーンテーブルを1つあげて、もしその中にリングが含まれているならば、そのチェーンテーブルのリングの入り口の接点を見つけてください、さもなくばnullを出力します.
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */
構想:高速ポインタ、高速ポインタは毎回2つの長さを前進し、遅いポインタは毎回1つの長さを前進し、リングが存在すれば、必ずリング内で出会う.始点からリング入口までの長さa、リング入口から出会い点までの長さb、出会い点からリング入口までの長さc、リング長さrを仮定すると、2(a+b)=a+b+nr a+b=nr a+r-c=nr a=c+(n-1)rの関係があるので、リングが存在する場合、2つのポインタをそれぞれ出会い点とヘッドから出発させ、出会い点をリング入口とする
コード:
class Solution {
     
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
     
        if(NULL == pHead || NULL == pHead->next)
        {
     
            return NULL;
        }
        ListNode * slow = pHead;
        ListNode * fast = pHead;
        
        while(NULL != fast && NULL != fast->next)
        {
     
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
     
                return GetEntryNodeOfLoop(fast, pHead);
            }
            
        }
        return NULL;
    }
    
    ListNode* GetEntryNodeOfLoop(ListNode* fast, ListNode* pHead)
    {
     
        
        while(fast != pHead)
        {
     
            fast = fast->next;
            pHead = pHead->next;
        }
        return fast;
    }
};