C++の連結リストでn/k番目（分数）ノードを効率的に検索する方法

単方向連結リストと整数 k が与えられたとき、リスト内の要素数を n として、n/k 番目の要素を求める関数を作成することを考えます。割り算の結果が小数になった場合は、切り上げた値を採用します。

たとえば、リストが 1, 2, 3, 4, 5, 6 で k = 2 の場合を考えてみましょう。このとき n = 6 なので、6/2 = 3 番目のノード、すなわち値 3 が出力されます。

アルゴリズムの考え方

この問題は、2つのポインタを組み合わせたテクニックで効率的に解くことができます。手順は次の通りです。

• temp と fracPoint という2つのポインタを用意し、それぞれ NULL とリストの先頭（start）で初期化します。
• temp ポインタが k 回移動するごとに、fracPoint ポインタを 1 回だけ進めます。

この方法の利点は、リスト全体を一度走査するだけで目的のノードを特定できる点です。事前にリストの長さ n を数えておく必要がないため、計算量は O(n) のまま抑えられます。

実装例（C++）

#include<iostream>
using namespace std;
class Node {
    public:
        int data;
        Node* next;
};
Node* getNode(int data) {
    Node* new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
Node* fractionalNodes(Node* start, int k) {
    if (k <= 0 || start == NULL)
        return NULL;
    Node* fracPoint = NULL;
    int i = 0;
    for (Node* temp = start; temp != NULL; temp = temp->next) {
        if (i % k == 0) {
            if (fracPoint == NULL)
                fracPoint = start;
            else
                fracPoint = fracPoint->next;
        }
        i++;
    }
    return fracPoint;
}
void printList(Node* node) {
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}
int main(void) {
    Node* start = getNode(1);
    start->next = getNode(2);
    start->next->next = getNode(3);
    start->next->next->next = getNode(4);
    start->next->next->next->next = getNode(5);
    int k = 2;
    cout << "List is: ";
    printList(start);
    Node* answer = fractionalNodes(start, k);
    cout << "\nFractional node is " << answer->data;
}

実行結果

List is: 1 2 3 4 5
Fractional node is 3

コードのポイント

• fractionalNodes() 関数では、カウンタ i を使いながらリストを走査し、i % k == 0 のタイミングで fracPoint を1ノードずつ進めています。
• k が 0 以下の場合やリストが空の場合は、安全のため NULL を返すようにしています。
• 上記の例では、リストの長さは n = 5、k = 2 なので、ceil(5/2) = 3 番目のノード、すなわち値 3 が出力されます。