C++でソート済み連結リストから中央値を求める方法

この問題では、N個の要素からなるソート済み連結リスト（ソートされたリンクリスト）が与えられ、その中央値を求めることが課題となります。

ソート済み連結リストと中央値とは

ソート済み連結リストとは、すべての要素が特定の順序で並べ替えられたシンプルな連結リストのことです。

例： 4 -> 6 -> 7 -> 9 -> NULL

中央値は、連結リストの中央に位置する要素です。求め方は以下の通りです。

• Nが奇数の場合：中央値は (n/2) 番目の要素
• Nが偶数の場合：中央値は (n/2) 番目の要素と (n/2 + 1) 番目の要素の平均値

具体例で理解しよう

入力： 2 -> 3 -> 4 -> 6 -> 9 -> NULL
出力： 4

このリストは5個の要素を持つため奇数となり、(5/2) 番目＝3番目の要素「4」が中央値になります。

解法アプローチ①：要素数を数えて再度走査する方法

最もシンプルな解決策は、連結リストを走査してすべての要素をカウントすることです。

1. カウント結果が奇数の場合：もう一度リストを走査し、N/2 番目の要素を取得します。
2. カウント結果が偶数の場合：N/2 番目と N/2 + 1 番目の要素まで走査し、その2つの値を足して2で割ります。

解法アプローチ②：2ポインタを使う効率的な方法

もうひとつのアプローチとして、2つのポインタによる走査を利用すると、事前に要素数をカウントせずに中央値を見つけることができます。

pointer1 と pointer2 の2つのポインタを用意し、条件に応じて次のように判定します。

• pointer1 が NULL でない場合：pointer2 が指すノードが中央値
• pointer1 が NULL の場合：(pointer2 の前のノードの値 ＋ pointer2 の値) ÷ 2 が中央値

これは「速いポインタ」と「遅いポインタ」を使うテクニックで、速いポインタがリストの末尾に到達したとき、遅いポインタはちょうど中央に位置します。

C++での実装例

上記の解法を実際に動かすプログラムは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void findMedianValue(Node* head){
    Node* ptr1 = head;
    Node* ptr2 = head;
    Node* prev = head;
    if (head != NULL) {
        while (ptr2 != NULL && ptr2->next != NULL) {
            ptr2 = ptr2->next->next;
            prev = ptr1;
            ptr1 = ptr1->next;
        }
        if (ptr2 != NULL)
            cout<<ptr1->data;
        else
            cout<<float(ptr1->data + prev->data) / 2;
    }
}
void pushVal(struct 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 main(){
   struct Node* head = NULL;
   pushVal(&head, 3);
   pushVal(&head, 5);
   pushVal(&head, 6);
   pushVal(&head, 8);
   pushVal(&head, 9);
   pushVal(&head, 11);
   cout<<"連結リストの中央値は ";
   findMedianValue(head);
   return 0;
}

実行結果

連結リストの中央値は 7

この例では、3 -> 5 -> 6 -> 8 -> 9 -> 11 という6個の要素（偶数）からなるリストに対して、中央の2つの値「6」と「8」の平均である 7 が出力されます。

まとめ

ソート済み連結リストの中央値を求めるには、要素数をカウントして再度走査する単純な方法と、2ポインタ走査で一度に求める効率的な方法があります。2ポインタ法を使えば、リスト全体の長さを事前に知らなくても、時間計算量 O(N)・空間計算量 O(1) で中央値を求められます。