C++で単方向連結リストの末尾からK番目のノードを効率的に検索する方法

連結リスト（リンクリスト）とは、複数のノードが互いに接続された線形データ構造です。各ノードは「データフィールド」と「次のノードへのアドレス」という2つの要素で構成されています。

ここでは、与えられた単方向連結リストの中から末尾からK番目のノードを見つける方法を解説します。

問題の例

入力：

1→2→3→4→7→8→9
K = 4

出力：

末尾から4番目のノード：4

説明：この単方向連結リストにおいて、末尾から4番目に位置するノードは「4」であるため、出力として「4」を返します。

解決のためのアプローチ

連結リストの各ノードにはデータと次のノードへのアドレスが格納されています。末尾からK番目のノードを求めるには、2つのポインタを使ったテクニックが有効です。最初に、両方のポインタを連結リストの先頭（ヘッド）に設定します。

まず一方のポインタ（fast）だけをKステップ先に進めます。その後、fastポインタがリストの末尾に到達するまで、もう一方のポインタ（slow）と共に両方を同時に進めていきます。このとき、slowポインタが指している位置こそが、末尾からK番目のノードとなります。

アルゴリズムの手順

• 関数 kthFromtheEnd(node* head, int k) は、ヘッドノードへのポインタと位置Kを引数として受け取り、末尾からK番目のノードの値を出力します。

• 2つのポインタ slow と fast を用意し、どちらも最初はヘッドを指すようにします。

• fast ポインタをK回前方へ移動させます。

• fast ポインタがNULL（リストの終端）に達するまで、slow と fast の両方を1ステップずつ同時に進めます。

• ループ終了時点で slow が指しているノードが、末尾からK番目のノードとなるため、その値を返します。

C++での実装例

#include<iostream>
using namespace std;
class node{
public:
    int data;
    node*next;
    node(int d){
        data=d;
        next=NULL;
    }
};
void insertAthead(node*&head,int d){
    node*n= new node(d);
    n->next= head;
    head=n;
}
void printList(node*head){
    while(head!=NULL){
        cout<<head->data<<"-->";
        head= head->next;
    }
}
void kthFromtheEnd(node*head, int k){
    node*slow= head;
    node*fast= head;
    for(int i=0;i<k;i++){
        fast= fast->next;
    }
    while(fast!=NULL){
        slow= slow->next;
        fast= fast->next;
    }
    cout<<"末尾から"<<k<<"番目のノード："<<slow->data<<endl;
}
int main(){
    node*head= NULL;
    insertAthead(head,2);
    insertAthead(head,4);
    insertAthead(head,5);
    insertAthead(head,6);
    insertAthead(head,7);
    printList(head);
    cout<<endl;
    kthFromtheEnd(head,4);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

7-->6-->5-->4-->2-->
末尾から4番目のノード：6

説明：この連結リストは 7→6→5→4→2 であり、Kの値は「4」です。末尾から4番目に位置するノードは「6」であるため、「6」が出力されます。

計算量について

この手法では、連結リストを一度走査するだけで目的のノードを見つけられるため、時間計算量はO(N)、必要な追加メモリはポインタ2つ分のみでO(1)となります。リストの長さを事前に求める必要がないため、非常に効率的なアプローチと言えます。