6

[編集]私のコードを修正しました。while（temp！= NULL）であり、while（temp-> next！= NULL）ではありません。間違ったコードを挿入して申し訳ありません。

今日、私はオンラインプログラミングテストに参加しました。インタビュアーはCodi​​lityを使用して、私のコードと他のインタビュイーを評価しました。ある瞬間、リンクリストについての質問がありました。リンクリストにあるアイテムの数を数えようとしています。私はこれを行うための唯一の可能なアプローチ、AFAIKを行いました：

//This is struct declaration
struct SomeStruct
{
    int value;
    SomeStruct* next;
}

int elementCount(SomeStruct* list)
{
    int count = 0;
    if(list != NULL)
    {
        SomeStruct* temp = list;
        while(temp != NULL)
        {
            count++;
            temp = temp->next;
        }
    }
    return count;
}

この質問への回答としてこのコードを送信したとき、Codilityは、タスクの実行に時間がかかりすぎるため、このソリューションは間違っていると指摘しました。私の頭とSOのこのスレッドでは、単純な方法ではなく、リンクリストをトラバースせずにサイズを取得する他の方法はありません。

この解決策が間違っていると書かれている場合、Codilityに問題がありますか？または別のアプローチがありますか？

PS：STLの使用を許可されたテスト

4

3 に答える 3

6

実際の数より1少ない数を返すため、ソリューションは正しくありません。1つの要素を持つリストに適用してみてください。

なぜあなたはこの奇妙な2層構造を思いついたのですifかtemp->next？なぜだけではないのですか

unsigned elementCount(const SomeStruct *list)
{
  unsigned count = 0;
  for (const SomeStruct *temp = list; temp != NULL; temp = temp->next)
    ++count;
  return count;
}

listが指す要素を未使用の予約済みの「ヘッダー」要素として扱うことにしたのではないかと思います。実際、リストをそのように実装することが理にかなっている場合があります。しかし、私はあなたの投稿にそのようなことは何も述べられていません。彼らはそれを具体的にそのように扱うようにあなたに言いましたか？

于 2012-11-15T01:04:52.997 に答える
3

反復ごとに間接参照temp->next を2回評価する必要はありません。

あなたは簡単に行うことができます

int count( SomeStruct const* pNode )
{
    int result = 0;
    while( pNode != 0 )
    {
        ++result;
        pNode = pNode->next;
    }
    return result;
}

また、WhozCraigが指摘しているように、コードは論理的に間違っていて（1つの結果でオフになります）、潜在的に非効率的であるだけではありません。

于 2012-11-15T01:01:13.910 に答える
2

Codilityは、循環リンクリストを使用してチェックしている可能性があります。この場合、コードは決して終了しません。

ただし、STLを使用すると、sizeメソッドを使用したList <>があるため、これは簡単になります。

于 2012-11-15T01:02:17.533 に答える