大神の進級の道----チェーン時計(SECOND)

チェーン時計のリングは解決しにくいですか?三つの問題をはっきりさせておけば分かる.**1.単一チェーンテーブルにループがあるかどうかを判断します.もし環を持っているならば、環の長さを求めますか?環の入り口の点を求めますか?2.2つのチェーンテーブルが交差しているかどうかを判断し、交差している場合は交点を求める.(チェーンテーブルにループがないと仮定する).2つのチェーンテーブルが交差しているかどうかを判断し、交差している場合は、交点を求めます.(チェーンテーブルにループがある可能性があると仮定)【アップグレード版】**
1.ループスピードポインタがあるかどうかを判断し、出会えるならループ

ListNode* IsCycle(ListNode* plist)  
{  
    ListNode* fast = plist, *slow = plist; //         

    while(fast && fast->next)  
    {  
        fast = fast->next->next;  
        slow = slow->next;  
        if(fast == slow)  
        {  
            return slow;  
        }  
    }  

    return NULL;  
}  

2.リングの長さを求める考え方:スナップポインタの出会い点から一周し、カウンタでカウントする

int GetCycleLen(ListNode* plist)  
{  
    //           ，      0 
    ListNode* meet = IsCycle(plist);  

    if(meet)  
    {  
        int count = 1;  
        ListNode* cur = meet->next;  
        while(meet != cur)  
        {  
            cur = cur->next;  
            count++;  
        }  
        return count;  
    }  

    // meet  (   )，  0 
    else  
    {  
        return 0;  
    }  
}  

3.入口点を判断する考え方:ヘッドノードから入口点までの距離L、入口点から出会い点までの距離Xを設定し、ループ長Cはスローポインタの2倍であり、かつ出会い点で出会うので、2(L+X)=L+X+C*n(クイックポインタリードループ数)解L=n*C-Xなので、スローポインタの出会い点からヘッドノードと一緒に歩く、彼らの出会い点が入口点である

ListNode* GetCycleEntry(ListNode* plist)  
{  
    ListNode* meet = IsCycle(plist);  
    if(meet)  
    {  
        while (meet != plist)  
        {  
            meet = meet->next;  
            plist = plist->next;  
        }  
        return plist;  
    }  
    else  
    {  
        return NULL;  
    }  
}  

4.リングレスチェーンテーブルの交差構想:2つのチェーンテーブルの長さ差の絶対値gabを計算し、長いチェーンテーブルはまずgabステップを移動し、それから2つのチェーンテーブルは一緒に歩く.エンディングまで行く前に出会ったら、その出会い点が交点

ListNode* GetmeetNode(ListNode* list1, ListNode* list2)//          

{
    //         
    //      
    //              gab，       gab ，
    //         。            ，         
    ListNode* cur1 = list1;
    ListNode* cur2 = list2;
    int len1 = 0, len2 = 0;
    while (cur1)
    {
        len1++;
        cur1 = cur1->next;
    }
    while (cur2)
    {
        len2++;
        cur2 = cur2->next;
    }
    ListNode* longlist = list1;
    ListNode* shortlist = list2;
    if (len1 < len2)
    {
        longlist = list2;
        shortlist = list1;
    }
    int gap = abs(len1 - len2);
    while (gap--)
    {
        longlist = longlist->next;
    }
        while (longlist)
        {
            if (longlist = shortlist)
            {
                return longlist;
            }
            longlist = longlist->next;
            shortlist = shortlist->next;

        }
        return NULL;
    }

5.任意の2つのチェーンテーブルは交差を判断する:1)2つともリングを持たない;2)そのうちの1つのバンドリング;3)両方ともリング付き

ListNode* IsCross(ListNode* plist1, ListNode* plist2)  
{  
    ListNode* ent1 = GetCycleEntry(plist1);  
    ListNode* ent2 = GetCycleEntry(plist2);  

    //1.      ，          
    if (ent1 == NULL && ent2 == NULL)  
    {  
        return IsCrossNoCycle(plist1, plist2);  
    }  

    //2.      ，      
    else if ((ent1 == NULL && ent2) || (ent2 == NULL && ent1))  
    {  
        return NULL;  
    }  

    //3.      
    // 1)    
    // 2)   
    // 3)   

    else  
    {  
        //1)         ，   ，          
        if(ent1 == ent2)  
        {  
            ent1->next = NULL;  
            return IsCrossNoCycle(plist1, plist2);  
        }  

        else  
        {  
            //2)  ，      
            //     ：           ，             
            //       plist1     
            ListNode* cur = ent1->next;  
            while (cur != ent1)  
            {  
                if(cur == ent2)  
                {  
                    return ent1;  
                }  
                cur = cur->next;  
            }  
            return NULL;    //    
        }  
    }  
}