C++で連結リストのモジュラーノードを検索する方法を解説

この問題では、片方向連結リスト L と数値 k が与えられます。求められるのは、連結リストの中から「モジュラーノード」を見つけ出すことです。

問題の概要

モジュラーノードとは、ノードのインデックス i が k で割り切れる（i % k == 0）ノードのうち、最後尾に近いものを指します。つまり、条件を満たすノードの中で最も後ろにあるノードを返す必要があります。

入出力の例

具体的な例で問題を確認してみましょう。

入力

ll = 3 -> 1 -> 9 -> 6 -> 8 -> 2, k = 4

出力

6

解説

要素 6 はインデックス 4 の位置にあり、4 は k = 4 で割り切れます。

このリストにはインデックス 1〜6 のノードがありますが、そのうち 4 の倍数となるインデックスは「4」だけなので、該当する要素 6 が答えとなります。

解決アプローチ

最もシンプルな解法は、カウンター変数を使って連結リストの先頭から順にノードを数えていく方法です。走査中に i % k == 0 を満たすノードが見つかるたびに、それを「モジュラーノード」として記録し更新していきます。走査が終了した時点で記録されているノードが、条件を満たす最後のノードということになります。

計算量は O(n)、必要な追加メモリは O(1) であり、非常に効率的です。

C++による実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* newNode(int data) {
    Node* new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

Node* findModularNodeLL(Node* head, int k) {
    if (k <= 0 || head == NULL)
        return NULL;
    int i = 1;
    Node* modNode = NULL;
    for (Node* currNode = head; currNode != NULL; currNode = currNode->next) {
        if (i % k == 0)
            modNode = currNode;
        i++;
    }
    return modNode;
}

int main() {
    Node* head = newNode(3);
    head->next = newNode(1);
    head->next->next = newNode(9);
    head->next->next->next = newNode(6);
    head->next->next->next->next = newNode(8);
    head->next->next->next->next->next = newNode(2);

    int k = 4;
    Node* modularNode = findModularNodeLL(head, k);

    cout << "連結リストのモジュラーノードは ";
    if (modularNode != NULL)
        cout << modularNode->data;
    else
        cout << "見つかりませんでした";
    return 0;
}

実行結果

連結リストのモジュラーノードは 6

まとめ

このアルゴリズムのポイントは以下の通りです。

• k が 0 以下の場合やリストが空の場合は NULL を返してエラーに対応します。
• インデックスは 1 から始めるため、i の初期値は 1 とします。
• 条件を満たすノードが見つかるたびに modNode を上書きすることで、自動的に最後の該当ノードが残ります。

このように、一度の走査でモジュラーノードを効率よく求めることができます。