単独リンクリストの中間ノード

Question

このコードはC++でリストの中間ノードを表示するのには見つかりましたが、コードを理解できません...誰かが私に説明できますか？

Type& findMiddleNode() 
{ 
    int check = 0; 
    nodeType *current; 
    nodeType *mid; 

    current = first; 
    mid = first; 

    while (current != NULL) 
    { 
     current = current->link; 
     check = (check + 1) % 2; 

     if (check == 0) 
      mid = mid->link; 
    } 

    return mid->info; 
} 

PD：このコードは完璧に動作しますが、わかりません。誰かが私にこれを理解するのを助けます。ありがとう！

Answer 1

基本的な考え方は、リストを介して2つのポインタBとAを移動させることであるが、BでA.

声明

check = (check + 1) % 2; 

＆hellipの唯一の半分の速度で移動します。 checkには値0,1,0,1などが与えられ、2回目のAの移動ごとにBを移動するために使用されます。

単一のリンクリストにループが含まれているかどうかを確認するための質問に対する可能な（考えられる）答えがあります。この場合、高速移動ポインタは両方がループに入った後に遅いポインタに追いつくでしょう。

---

だけプログラムによって消費同じ仕事についてで、同じことを行うための簡単な方法は、（1）ノードNの数をカウントし、そして（2）再び開始時に開始するありますノード番号n/2に移動します。

ステップは、（1）上記のように、ポインタをN回移動させ、ステップ（2）上記Bのように、ポインタをN/2倍を移動させます。