[SCU 2016年問題]並べ替えられた2つの単一チェーンテーブルがあり、問題を統合

2056 ワード

2016年の試験問題を思い出した.
2つの単一チェーンテーブルがあり、すでに非減算でソートされており、2つのチェーンテーブルのマージを完了する必要があり、非減算でソートされ、現在の2つのチェーンテーブル以外のストレージスペースは使用できません.
 ここでは、重複する要素の存在を許可します.
たとえば、ha->(1)->(3)->(8);hb->(1) -> (7) -> (9)  .
マージ後、ha->(1)->(1)->(3)->(7)->(8)->(9)を得るべきです.
タイトルには余分なストレージスペースの使用が許されないことが要求されているため、2つのチェーンテーブルの要素を3番目のチェーンテーブルに直接書き込むサボりは通用しません.
解決策:2番目のチェーンテーブルの要素を順番に1番目のチェーンテーブルの現在位置に挿入するかどうかを判断する.s 1,s 2はそれぞれ第1のチェーンテーブルを指し、t 1,t 2はそれぞれ第2のチェーンテーブルを指す.
t 1の値がs 2の値より大きい場合、s 1とs 2は順次後方に移動し、サイクル後に判断する.
t 1の値がs 2より小さい場合、t 1がs 1とs 2の間に挿入されることを示す.t 1はt 2となり、t 2はt 1の後続をプログラミングする.
ループの終了条件は、s 2またはt 2のいずれかがNULLになることであり、チェーンテーブルの1つが終了したことを示す.
コードは次のとおりです.テストに合格しました.
typedef struct header
{
    int V;
    struct header * pnext;
} Node;

Node * link_merg(Node * p1, Node *p2)
{
    Node *s1=p1, *s2, *t1=p2, *t2;
    
    if(s1->V > t1->V)
    {
        Node * tmp = t1;
        t1 = s1;
        s1 = tmp;
    }
    s2 = s1->pnext;
    t2 = t1->pnext;
    
    while((s2!=NULL)&&(t2!=NULL))
    {
        if(s2->V > t1->V)
        {
            s1->pnext = t1;
            t1->pnext = s2; //  t1        
            s1= t1;
            s2 = s1->pnext;
            t1 = t2;
            t2 = t1->pnext;
        }
        else
        {
            s1 = s2;
            s2 = s1->pnext;
        }
    }
    if(s2==NULL)
    { s1->pnext = t1;}
    else
    {s2->pnext = t1;}
    return(s1);
}

帰ってきてまたこの問題を考えて、もう一つの良い方法があることを発見して、直接2つのチェーンテーブルを合併して、それから全体の大きいチェーンテーブルに対して並べ替えて、泡が出ても、急速に並べ替えてもいいです.
これにより、問題の要件にも合致し、他の追加のストレージスペースは使用されません.
汗ですね~その時は緊張しすぎて反応しませんでした...