C++でリンクリストのN番目のノードを取得する関数の実装方法

ここでは、リンクリスト（連結リスト）とインデックスが与えられたときに、リスト内のN番目のノードを取得する関数をC++で実装する方法を解説します。

まず、具体的な例を使って問題を確認しましょう。

入力例

linked list = 34 -> 4 -> 9 -> 1 , n = 2

出力例

9

この場合、インデックス2（0始まり）にあるノードのデータ「9」が出力されます。

解決のアプローチ

n番目のノードへアクセスするには、リンクリストの先頭ノードから順にポインタをたどりながらインデックスのカウントを増やしていき、目的のn番目の位置に到達した時点でそのノードのデータを返します。

処理の手順

1. 先頭ノードへのポインタを現在位置として設定し、カウントを0で初期化します。
2. 現在のノードがNULLでない限り、ループを繰り返します。
3. カウントが指定されたインデックスと一致したら、そのノードのデータを返します。
4. 一致しなければカウントを1増やし、次のノードへ移動します。

このアルゴリズムの計算量はO(n)であり、リストの長さに比例して処理時間が増加します。

プログラム例

#include <iostream>
using namespace std;
class Node{
    public:
    int data;
    Node* next;
};
void insertNode(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
int findNodeAt(Node* head, int index) {
    Node* current = head;
    int count = 0;
    while (current != NULL){
        if (count == index)
            return(current->data);
        count++;
        current = current->next;
    }
}
int main(){
    Node* head = NULL;
    insertNode(&head, 8);
    insertNode(&head, 2);
    insertNode(&head, 9);
    insertNode(&head, 1);
    insertNode(&head, 4);
    int n = 2;
    cout<<"Element at index "<<n<<" is "<<findNodeAt(head, 2);
    return 0;
}

実行結果

Element at index 2 is 9

コードの解説

insertNode関数は、新しいノードを動的に生成し、リストの先頭に挿入する補助関数です。データを挿入するたびに先頭に追加されるため、main関数では挿入した順序と逆の並び（4 → 1 → 9 → 2 → 8）のリンクリストが構築されます。

findNodeAt関数が本題のN番目のノードを取得する関数です。headからcurrentポインタを順に進めながらcountを増やしていき、countがindexと一致した時点でそのノードのdataを返します。

なお、実務上は指定されたインデックスがリストの範囲外の場合のエラー処理（例外の送出や-1などの特殊値の返却）を追加すると、より堅牢な実装になります。