アルゴリズム学習5---出力チェーンテーブルの最後からk番目のノード

タイトル:
1つの一方向チェーンテーブルを入力して、このチェーンテーブルの中で最後からk番目のノードを出力して、チェーンテーブルの最後から0番目のノードはチェーンテーブルの最後のポインタです
アルゴリズムの構想:2つのポインタpを定義して、qZはチェーンの表の頭を指して、それからqをk個のオフセット量を後ろに移動させて、この時p、qの差の距離はkで、それから更にp、qを同時に後ろに移動させて、qがチェーンの表の尾を指すまで、この時pの値は要求したのです
アルゴリズム擬似コード

initialize 2 pointer,let them point to link's head

let q move index k

//now p is differ k with q
when q get into the end, the p's position is we want
return p's data

C++実装

//initialize 2 pointer
    ChainNode<T> *p, *q;
    p = q = first;

    //let q move index k
    for(int i = 0; i != k; ++i)
    {
        q = q->link;
    }

    //now p is differ k with q
    //when q get into the end, the p's position is we want
    while(q != NULL)
    {
        p = p->link;
        q = q->link;
    }
    
    //return p's data
    return p->data;