C++で連結リストの中央から先頭に向かってk番目のノードを検索する方法

問題概要

この問題では、連結リスト(Linked List)と数値kが与えられます。求めるのは、連結リストの中央ノードから先頭(Head)に向かってk番目にあるノードです。

具体例を使って問題を確認してみましょう。

入力: 連結リスト: 4 → 2 → 7 → 1 → 9 → 12 → 8 → 10 → 5、k = 2

出力: 7

解説:

まず、中央ノードの値は 9 です。

そして、中央から先頭に向かって2番目のノードは 7 になります。

解法のアプローチ

連結リストの中央から先頭に向かってk番目の要素を見つけるには、まずリストを先頭から末尾まで一度走査し、ノードの総数nを求めます。

すると、中央から先頭に向かってk番目の要素は、先頭から数えて(n / 2 + 1 − k)番目の要素に相当することが分かります。

アルゴリズムの手順

1. リストを走査してノード総数nを取得します。
2. 中央の位置は n / 2 + 1 として計算できます(ノード数が偶数・奇数のどちらの場合でも機能します)。
3. 目的のノードの位置は (n / 2 + 1 − k) 番目です。
4. 計算結果が0以下になる場合(kが範囲外の場合)は -1 を返します。
5. 先頭から目的の位置まで再度走査し、該当ノードの値を返します。

このアルゴリズムの計算量は、リストを最大2回走査するため O(n) となり、追加のメモリ領域は不要で空間計算量は O(1) です。

ソリューションの実装例

#include <iostream>
using namespace std;

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

void pushNode(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int findKmiddleNode(struct Node* head_ref, int k) {

    int n = 0;
    struct Node* counter = head_ref;
    while (counter != NULL) {
        n++;
        counter = counter->next;
    }
    int reqNode = ((n / 2 + 1) - k);

    if (reqNode <= 0)
        return -1;

    struct Node* current = head_ref;
    int count = 1;
    while (current != NULL) {
        if (count == reqNode)
            return (current->data);
        count++;
        current = current->next;
    }
}

int main()
{
    struct Node* head = NULL;
    int k = 2;
    pushNode(&head, 5);
    pushNode(&head, 10);
    pushNode(&head, 8);
    pushNode(&head, 12);
    pushNode(&head, 9);
    pushNode(&head, 1);
    pushNode(&head, 7);
    pushNode(&head, 2);
    pushNode(&head, 4);

    cout<<k<<"番目の要素(中央から先頭へ): "<<findKmiddleNode(head, k);

    return 0;
}

出力結果

2番目の要素(中央から先頭へ): 7

コードの解説

上記のプログラムでは、pushNode関数が新しいノードをリストの先頭に挿入していきます。findKmiddleNode関数は、まず最初のwhileループでリスト全体を走査してノード数nをカウントし、次に (n / 2 + 1 − k) で目的の位置reqNodeを算出します。reqNodeが0以下の場合は有効なノードが存在しないため -1 を返し、そうでなければ2回目の走査で該当位置のノードの値を返します。