データ構造のシングルチェーン表の交差とリングの問題

データ構造のシングルチェーン表の交差とリングの問題
一、シングルチェーン表はベルト交差しない
もし二つのチェーン表にリングがないなら、それらの交差を以下の二つの状況に分けることができます.T型、V型
1.Tタイプ
このような形式の交差とは、単一のチェーンテーブルの最後を指しています.(ここでは尾だけで、頭ではなく)別のチェーンテーブルの中間位置を指しています.
2.Vタイプ
このような形の交差とは、別のシングルチェーンテーブルの最後を指しているシングルチェーンテーブルのことです.注目すべきはここではシングルチェーン表の最後を指すしかないです.もしシングルチェーン表の頭を指すなら、二つのシングルチェーン表は実際にはもっと大きなシングルチェーン表です.
3.交点を判断する
この二つの交差形の結果は同じです.もし交わると、二つのチェーンの最後の結点は必ず同じです.私たちはそれぞれ二つのチェーンを通して、最後の接合点を判断すればいいです.時間の複雑さはO(len 1＋len 2)であり、空間の複雑さはO(1)コードであるため、必要以上に説明されていない.
4.交点を求める
交点を要求するなら、ちょっと複雑です.二つのチェーンが交差すると、二つのチェーンの長さをそれぞれ求められます.二つのチェーンの長さの差をsubと表記します.長いチェーンの針を先にsub歩で進めて、二つのチェーンの針を同期させていけば、必ず交差点に行きます.
コードの実現において柔軟性があります.2つのチェーンの長さを求めた後、2つのチェーンの針を後ろに移動させる過程で、NULLの位置にポインタが来たかどうかを判断します.もし、二つのチェーンが全然交わらないと説明します.二つのチェーンの長さを求める時、ついでに二つのチェーンの最後の結点を比較して、交差するかどうかを判断させることもできます.交わらないなら、交点を求めなくてもいいです.
ここで使用する第二の案:

PNode GetCorssNode(PNode pHead1, PNode pHead2)
{
    PNode pN1 = pHead1;
    PNode pN2 = pHead2;
    int len1 = 0;
    int len2 = 0;
    if (pHead1 == NULL || pHead2 == NULL)   //         ，   
    {
        return NULL
    }
    while(pN1)  //         
    {
        len1++;
        pN1 = pN1->next;
    }
    while(pN2)  //         
    {
        len2++;
        pN2 = pN2->next;
    }
    if (pN1 == pN2) //     ，    。       NULL
    {
        int count = len1-len2;
        pN1 = pHead1;
        pN2 = pHead2;
        if (len1>=len2) //       ，            
        { 
            while(count>0)
            {
                pN1 = pN1->next;
                count--;
            }
        }
        else            //       ，            
        {
            while(count<0)
            {
                pN2 = pN2->next;
                count++;
            }
        }
        while(pN1 && pN2)   //      ，       
        {
            if (pN1 == pN2)
            {
                return pN1;
            }
            pN1 = pN1->next;
            pN2 = pN2->next;
        } 
    }
    return NULL;
}

二、シングルチェーンのバンドリング
シングルチェーンのベルトリングには以下のような種類があります.6型、0型
1.6型
2.0型(自環)
3.判断リング
判断リングには小さなテクニックがあります.二つのポインタをセットして、最初はチェーンの頭を指します.一つの針を一歩ずつ歩かせます.もう一つのポインタを二歩ずつ歩かせます.チェーンがもしリングを持っていたら、自環であろうとなかろうと、必ずリングの中で両針が出会います.環をしないなら、その二つの針は無限に循環しているのではないかと思うかもしれない.実はそうではないです.もしシングルチェーンの時計にリングが付いていないなら、速く歩く針は必ずNULLに行きます.

PNode IsListWithCircle(PNode pHead1)  //          ，     。
{
    PNode pFas = NULL;
    PNode pSlo = NULL;
    if (pHead1 == NULL)
    {
        return NULL;
    }
    pFas = pHead1;
    pSlo = pHead1;
    while(pFas && pFas->next)
    {
        pSlo = pSlo->next;
        pFas = pFas->next->next;
        if (pFas == pSlo)
        {
            return pFas;
        }
    }
    return NULL;
}

4.環の入り口を求める点
自環の場合は、どの結点も入り口と見なされます.二つの針を使って、一つは固定して、一つは後ろへ行って、この輪は自環であると判断すればいいです.
自輪でないと、つまり「6」ということになります.図のように:
赤い点は入り口の点で、緑の点はリングを判断する時の最後の交差点です.初めの結点から入り口の結点までの長さをLとし、入り口点から両針の交点までの長さをXとし、環の周囲をRと記す.
リングが交差していると判断した時、私たちは一つの針を一回歩かせます.他の針を一回に二歩歩かせます.二つの針が出会った時、速い針が歩く距離は必ず遅い針が歩く距離の2倍です.
右のような関係があります.2*(L+x+z*R)=L+x+m*Rは上式を簡略化して整理します.L=R-X+(n-1)*R
ここのL+X+z*Rはスローポインタで歩く距離で、L+X+m*Rは速いポインタで歩く距離で、zとmはそれぞれスローポインタと速いポインタで回る丸の数です.nはm-2*zに等しい
上の式によって、私達は2つの指針を設けて、1つは初めから、もう1つは出会いの点(緑の点)から始めて、2つの指針は一回すべて1回が歩くのです.最初から出発する針がリングの入り口(赤点)に来た時、出会いのポイントから出発する針は、何周か回った後、同じようにリングの入り口に来ます.

PNode GetCircleEnter(PNode pHead1, PNode pMeetNode)    //        
{
    PNode pHea = pHead1;
    PNode pMee = pMeetNode;
    if(pMeetNode == NULL)
        return NULL;
    while(1)
    {
        if (pHea == pMee)
        {
            return pHea;
        }
        pHea = pHea->next;
        pMee = pMee->next;
    }
}

三、シングルチェーンのバンドリングが交差する
1.交わっているかどうかを判断する
チェーンブレスレットの場合、状況がもっと複雑に見えるが、実は簡単なので、分析してみます.
シングルチェーンのバンドリングの交差状況は一つしかないです.二つのシングルチェーンの表が全部リングを持っている時だけ、交差することができます.もし一つのリングを持っていて、もう一つのリングを持たないと、どんな結果が出ますか?以下は図で説明する.
図に示すように、一つのリボンのもう一つのリングを持たない交差は上記の四つの場合だけです.
図1:一つのチェーンブロックを持たないで、最後にリングチェーンの頭を受けました.二つのチェーンのように見えますが、実はチェーンの一つです.図二:リングなしのチェーンは、リングチェーンのリングの入り口に接続されています.このようにしますと、赤不带环チェーンは図2の右側の赤いリボンチェーンに相当します.つまり、図二は実は二つのリボンで構成されています.図3:リングを持たないチェーンの末尾にリングチェーンの輪が付いています.この本質はまだ二つのリングチェーンです.図4:リングを持たないチェーンの末尾に自環リンクリストが接続されています.これはやはり二つのリングチェーンと見なしてもいいです.もう一つのケースは描かれていません.つまり、チェーンのない後部にチェーンの頭と環の入り口があります.これは実は2つのリングチェーンです.
したがって、全ての単一鎖のバンドリング交差問題は最終的には二つのリングチェーンの交差問題である.
私たちはこの二つのチェーンが全部リングを持っているかどうかを判断して、状況によって違った動作をすればいいです.ここでまとめてみます.1、2つは全部リングをつけないでください.1つだけのリングがあります.2つのチェーンは全部リングを持っています.交差すれば、2つのチェーンは必ず公共の輪があります.私達はただ1つのリングチェーンの中環の1つの結点を記録して、それから別のリングチェーンを遍歴して、それが記録されている結点と同じ結点があるかどうかを見ます.

int IsSListCross(PNode pHead1, PNode pHead2)    //             
{   
    PNode pTail1 = NULL;
    PNode pTail2 = NULL;
    if (pHead1 == NULL || pHead2 == NULL)   //         ，   
    {
        return -1;
    }
    pTail1 = pHead1;
    pTail2 = pHead2;
    while(pTail1)       //           
    {
        pTail1 = pTail1->next;
    }
    while(pTail2)       //           
    {
        pTail2 = pTail2->next;
    }
    if (pTail1 == pTail2)   //             
    {
        return 1
    }
    return 0;
}

int IsSListCrossWithCircle(PNode pHead1, PNode pHead2) //            ，      
{
    PNode p1 =  IsListWithCircle(pHead1);
    PNode p2 =  IsListWithCircle(pHead2);
    if (p1 == NULL && p2 == NULL)   //       
    {
        return IsSListCross(p1, p2);
    }
    if (p1 && p2)   //      
    {
        int n = GetCircleLen(pHead1);   
        while(n--)
        {
            if (p1 == p2)
            {
                return 1;
            }
            p1 = p1->next;
        }
    }
    return -1;
}

2.交差する2つのリボンチェーンの交差点を求めます.
上記では、リング付きのシングルチェーンが交差しているかどうかを判断した時、私達はそれぞれ2つのチェーンのリングの入り口を求めました.入り口の状況を比較して判断します.交点を求める時も、リングの入り口の点を利用して切り込むことができます.下の図のように、交差する2つのリングチェーンの可能な4つの交差点を示しています.図1:赤は2つのリングチェーンの交点で、黄色はそれらのリングの入口点です.二重リングチェーンはリングに達する前に交差します.図二:赤点は二重リングチェーンの入口点で、この点は同じ交点であると考えています.2つのリングチェーンはリングの上で交差します.図3:赤点は二重リングチェーンの交点で、この点は同じように二重チェーンのリングの入口点です.リングの入口点で交差する2つのバンドリング単一鎖計.図4:すなわち、リングチェーンが交差しているかどうかを判断する図4は、ここでは、2つのリングチェーンが完全に重なり合っていると考えられている.
分析によると、2つのリングチェーンの入り口点を取れば、上記の4つの状況を簡単に解決できます.2つのリングの入り口点が違っていれば、2つのリングのシングルチェーン表の交点はリングの入り口点です.二つのリングの入口点が同じなら、初めからリングの入り口点までそれぞれ二つのチェーン表を巡ります.遍歴中、リンクの長さは、最初からリングの入り口まで得られます.この長さを利用して、2つのリンク表の最初の同じ結点、つまり交点を求めることができます.

PNode MeetingNodeWithCircle(PNode pHead1, PNode pHead2) //         （    ）
{
    PNode pC1 = GetCircleEnter(pHead1, IsListWithCircle(pHead1));  //    1     
    PNode pC2 = GetCircleEnter(pHead2, IsListWithCircle(pHead2));  //    2     
    PNode pH1 = pHead1;
    PNode pH2 = pHead2;
    int len1 = 1;
    int len2 = 1;
    int SubLen = 0;
    if (pC1 != pC2)   //       
    {
        return pC1;
    }
    while(pH1 != pC1)   //                 
    {
        len1++;
        pH1 = pH1->next;
    }
    while(pH2 != pC1)   //                 
    {
        len2++;
        pH2 = pH2->next;
    }
    pH1 = pHead1;
    pH2 = pHead2;
    if (len1 >= len2)   //             SubLen 
    {
        SubLen = len1-len2;
        while(SubLen--)
        {
            pH1 = pH1->next;
        }
    }
    else
    {
        SubLen = len2-len1;
        while(SubLen--)
        {
            pH2 = pH2->next;
        }
    }
    while(pH1 != pH2)   //      ，              
    {
        pH1 = pH1->next;
        pH2 = pH2->next;
    }
    return pH1; //         
}