2

2つの指定されたリンクリストに同じデータが含まれているかどうかを確認する必要があります。この場合の順序は重要ではありません。つまり、{1,3,2}と{2,1,3}は同じです。counter=0新しい変数を導入して、次の手順を実行する必要があると思います。

while(node1->next!=NULL)
{
    int value=node1->value;
    if(contains(node2,value)){
        counter++;
    }

    node1=node1->next;

    if(counter== number of elements in node 1) 
        return true; 
    else return false;
}

もう1つの方法は、両方のリストを並べ替えて、ノードごとに比較することです。どちらが最適ですか？最初のケースではO（n ^ 2）操作が必要ですが、2番目のケースではNlog（N）+ O（N）のようになります（マージソートを使用する場合）。私は自分の考えで正しいですか？または、別の最適な方法はありますか？

4

5 に答える 5

2

あなたが投稿した2つの方法のうち、2番目の方が優れています。しかし、私はあなたに提案するでしょうhashing。

最初に最初のリンクリストをハッシュします。

ハッシュしながら2番目のリストを確認します。

このようにして、合計でO（n）時間で実行できます。

于 2012-04-12T16:19:02.300 に答える
2

リンクリストの値で許可されている場合は、最初のリンクの値を使用してヒストグラムを作成し、2番目のリストを繰り返し処理してヒストグラムエントリを減らします。最後にヒストグラムにゼロのみが含まれている場合、それらは同じです。

したがって、たとえば、list1に{1、3、4、2、4}が含まれている場合、ヒストグラムは（ゼロベース）[0、1、1、1、2]になります。

次に、list2に{1、3、2、4}が含まれている場合、ヒストグラムをデクリメントした後は[0、0、0、0、1]になります。

実行時間はO（m + n）になります

于 2012-04-12T16:19:40.920 に答える
1

このソリューションは同じ時間計算量を要しますが、それでも少し優れています！

{
 while(node1->next != NULL)
 {
    if(!contains(node2, node1->value)){
        return false;
    }
    node1 = node1->next;
 }
 return true;
}
于 2012-04-12T16:19:23.243 に答える
0

数字を文字列に出力してから、すべてが正しい順序になるように文字列を並べ替えることができます

編集：それはあなたの他の方法がより良いという単なる提案です

于 2012-04-12T16:32:45.593 に答える
0

これが間違いなく機能する再帰的なソリューションです。

int CompareLists(Node *headA, Node* headB)
{

if (headA == NULL && headB == NULL)     
{  return 1;  }
if (headA == NULL && headB != NULL)  
{  return 0;  }
if (headB != NULL && headB == NULL)  
{  return 0;  }
if (headA->data != headB->data)
{  return 0;  }

return CompareLists(headA->next, headB->next);  
}
于 2015-10-22T07:03:00.723 に答える