C++で再帰を使って単方向リンクリストの中央要素を求める方法

数値からなるリンクリストが与えられたとき、再帰処理を使ってリストの中央要素を求めることを考えます。例えば、リストの要素が [12, 14, 18, 36, 96, 25, 62] の場合、中央に位置する要素は 36 です。

アルゴリズムの考え方

この問題は「再帰でノード数を数え、戻りながらカウンタを減らす」というシンプルな発想で解くことができます。具体的な手順は以下のとおりです。

1. 再帰呼び出しを用いて、リスト全体のノード総数を数えます。
2. リストの末端（NULL）に到達した時点で、カウンタを半分にします。
3. 再帰から戻る過程で、呼び出しごとにカウンタ n を 1 ずつ減らします。
4. n が 0 になったノードを中央要素として記録します。

サンプルコード

#include<iostream>
using namespace std;
class Node {
public:
    int data;
    Node *next;
};
Node* getNode(int data) {
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
void midpoint_task(Node* head, int* n, Node** mid) {
    if (head == NULL) {
        *n /= 2;
        return;
    }
    *n += 1;
    midpoint_task(head->next, n, mid);
    *n -= 1;
    if (*n == 0) {
        *mid = head;
    }
}
Node* findMidpoint(Node* head) {
    Node* mid = NULL;
    int n = 1;
    midpoint_task(head, &n, &mid);
    return mid;
}
void append(struct Node** start, int key) {
    Node* new_node = getNode(key);
    Node *p = (*start);
    if (p == NULL) {
        (*start) = new_node;
        return;
    }
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = new_node;
}
int main() {
    Node *start = NULL;
    int arr[] = {12, 14, 18, 36, 96, 25, 62};
    int size = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < size; i++) {
        append(&start, arr[i]);
    }
    Node* res = findMidpoint(start);
    cout << "Mid point is: " << res->data;
}

実行結果

Mid point is: 36

コードの解説

NodeクラスとgetNode関数

Node クラスはノードの値（data）と次ノードへのポインタ（next）を保持します。getNode 関数は、指定された値を持つ新しいノードを生成して返します。

midpoint_task関数（再帰処理の中核）

再帰を進みながらノード数をカウントし、head が NULL に到達した時点でカウンタを半分にします。その後、再帰の巻き戻しのたびにカウンタを 1 減らし、0 になった位置のノードを中央要素として記録します。

findMidpoint・append・main関数

findMidpoint は midpoint_task を呼び出して中央ノードを取得します。append はリストの末尾にノードを追加する補助関数で、main 関数では配列の要素からリンクリストを構築し、求まった中央要素を出力します。

計算量について

時間計算量は O(n) です。また、再帰呼び出しに伴うスタック領域を消費するため、空間計算量も O(n) となります。なお、要素数が偶数の場合は、中央にあたる 2 つの要素のうち後ろ側が返される点に注意してください。