C++で片方向連結リスト内の最小値と最大値の要素を検索する方法

問題概要

この問題では、片方向連結リスト（単一リンクリスト）が与えられます。私たちのタスクは、リンクリスト内に存在する最小の要素と最大の要素を見つけることです。

問題を理解するための例を見てみましょう

入力

linked List : 5 -> 2 -> 7 -> 3 -> 9 -> 1 -> 4

出力

Smallest element = 1
Largest element = 9

解決アプローチ

この問題に対するシンプルな解決策は、リンクリストを先頭からノードごとに走査することです。手順は以下の通りです。

1. まず、minElement と maxElement を最初の要素の値（head->data）で初期化します。
2. 次に、リンクリストを1要素ずつ走査していきます。
3. 現在のノードの値を maxElement と比較し、より大きい値を maxElement 変数に格納します。
4. 同じ要領で、より小さい値を minElement 変数に格納します。
5. 走査が完了したら、両方の値を出力します。

リンクリスト全体を一度だけ走査すればよいため、時間計算量は O(n)、追加のメモリは不要で空間計算量は O(1) となります。

ソリューションの動作を示すプログラム

例

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void printLargestSmallestLinkedList(struct Node* head) {
    int maxElement = INT_MIN;
    int minElement = INT_MAX;
    while (head != NULL) {
        if (minElement > head->data)
            minElement = head->data;
        if (maxElement < head->data)
            maxElement = head->data;
        head = head->next;
    }
    cout<<"Smallest element in the linked list is : "<<minElement<<endl;
    cout<<"Largest element in the linked list is : "<<maxElement<<endl;
}
void push(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = (*head);
    (*head) = newNode;
}
int main() {
    struct Node* head = NULL;
    push(&head, 5);
    push(&head, 2);
    push(&head, 7);
    push(&head, 3);
    push(&head, 9);
    push(&head, 1);
    push(&head, 4);
    printLargestSmallestLinkedList(head);
    return 0;
}

出力

Smallest element in the linked list is : 1
Largest element in the linked list is : 9

まとめ

片方向連結リストの最小値と最大値を求めるには、リンクリストを先頭から末尾まで一度だけ走査し、各ノードの値を現在の最小値・最大値と比較して更新していくのが最も効率的な方法です。計算量は O(n) であり、リンクリストの基本的な走査パターンを学ぶのに最適な問題と言えます。