C++で循環片方向リンクリストから最小値と最大値を求める方法

本記事では、C++を使って循環片方向リンクリスト（単一循環リンクリスト）から最小値と最大値を検索する方法を解説します。

循環リンクリストの基本構造

循環リンクリストは、最後のノードのnextポインタが先頭ノードを指すデータ構造です。これにより、リスト全体がリング状につながります。また、startポインタによって先頭ノードの位置も管理されます。

新しい要素を挿入するときは、末尾ノードのnextに新ノードをつなぎ、新ノードのnextにstartノードのアドレスを設定します。これで循環構造が維持されます。

最小値・最大値を求めるアルゴリズム

考え方はとてもシンプルです。手順は以下の通りです。

• 変数 min を INT_MAX（int型の最大値）で、max を INT_MIN（int型の最小値）で初期化します。
• リストを先頭から順に走査します。
• 現在の要素が min より小さければ min を更新し、max より大きければ max を更新します。
• 走査が終わった時点で、min には最小値、max には最大値が格納されています。

この手法の計算量は O(n) で、リストを一度走査するだけで両方の値を取得できます。

C++による実装例

#include<iostream>
using namespace std;
class Node{
    public:
    int data;
    Node *next;
};
Node* getNode(int key){
    Node *newNode = new Node();
    newNode->data = key;
    newNode->next = NULL;
    return newNode;
}
void insert(Node **start, int data){
    Node *current = *start;
    Node *newNode = getNode(data);
    if(*start == NULL){
        newNode->next = newNode;
        *start = newNode;
        return;
    }
    while (current->next != *start) {
        current = current->next;
    }
    newNode->next = *start;
    current->next = newNode;
}
void displayList(Node *start){
    Node* current = start;
    if (start == NULL) {
        cout << "Display List is empty";
        return;
    } else {
        do {
            cout << current->data << " ";
            current = current->next;
        }
        while (current != start);
    }
    cout << endl;
}
void getMinMax(Node **start){
    if(*start == NULL){
        return;
    }
    Node* current;
    current = *start;
    int min = INT_MAX, max = INT_MIN;
    do {
        if (current->data < min) {
            min = current->data;
        }
        if (current->data > max) {
            max = current->data;
        }
        current = current->next;
    } while (current != *start);
    cout << "Minimum: " << min << ", Maximum: " << max;
}
int main() {
    int data[] = {99, 11, 22, 10, 44, 55, 66};
    int n = sizeof(data)/sizeof(data[0]);
    Node *start = NULL;
    for(int i = 0; i<n; i++){
        insert(&start, data[i]);
    }
    displayList(start);
    getMinMax(&start);
}

実装上のポイント： 循環リンクリストの走査では、while (current->next != start) のような条件にすると最後のノードが比較対象から漏れてしまうことがあります。do-while 文を使えば、全ノードを確実に1回ずつ処理できるため安全です。

出力結果

99 11 22 10 44 55 66
Minimum: 10, Maximum: 99

このように、循環リンクリストでも通常の線形リストと同様に、一度の走査で最小値と最大値を効率的に求めることができます。