インタビューのテストでLinkedListを使用しました

Question

[EDIT]自分のコードが修正されました。 while（temp - > next！= NULL）while（temp！= NULL）ではありません。間違ったコードを挿入して申し訳ありません。

今日、私はオンラインプログラミングテストに参加しました。インタビュアーはコードと他の面接者を評価するためにCodilityを使用しました。 しばらくして、リンクリストに関する質問がありました。リンクされたリストのアイテム数を数えようとしています。

私はこの質問に対する答えとして、このコードを送信するとき、私は覚えて

//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は、その実行にあまりにも多くの時間を消費するので、この解決策が間違っていることを私に指摘： は、私は私の知る限り、これを行うためにのみ可能なアプローチをしましたタスク。 私の頭の中で、this threadには、リンクされたリストのサイズを単純な方法ではなく通過させる他の方法はありません。

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

PS：テストは十分にあなたが二回反復ごとに間接temp->nextを評価する必要はありませんSTL

Answer 1

の使用許可しました。

あなたは、単に

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

を行うことができます。また、WhozCraig notesとして、あなたのコードは、単に潜在的に非効率的な（1つの結果によってオフをもたらす）、論理的に間違っていませんでした。

Answer 2

コーディネーションでは、循環リンクリストを使用してチェックすることができます。この場合、コードは決して終了しません。

しかし、これは、リスト<>とサイズメソッドを持つため、STL trivilailzesを使用しています。

Answer 3

解決策は正しくありません。実際の数より1少ない数を返します。それを1要素のリストに適用してみてください。

ifと、temp->nextをチェックするこの奇妙な2層構造を考え出したのはなぜですか？なぜだけではなく、

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

私はあなたが使用されていないと予約「ヘッダ」要素としてlistが指す要素を処理することを決定したと思われます。実際、そうした方法でリストを実装するのが理にかなっていることがあります。しかし、私はあなたのポストに述べられているようなものは何も見ません。彼らはあなたにそれを具体的に扱うよう伝えましたか？