C++で連結リストから2番目に大きい要素を検索する方法

連結リスト内の2番目に大きい要素とは

この記事では、連結リスト（リンクリスト）の中から2番目に大きい要素を効率的に求める方法を解説します。数値データを持つn個の異なるノードで構成されたリストを想定してください。例えば、リストが [12, 35, 1, 10, 34, 1] のような場合、最大値は35であり、その次に大きい値である 34 が求めるべき答えとなります。

このアルゴリズムは、配列から2番目に大きい要素を探す処理と基本的な考え方は同じです。リストを先頭から末尾まで一度だけ走査し、各ノードの値を比較しながら「最大値」と「2番目に大きい値」の2つの変数を順次更新していくことで、時間計算量 O(n)・空間計算量 O(1) という効率で答えを得られます。

アルゴリズムの流れ

• 最大値を保持する first_max と、2番目に大きい値を保持する second_max を用意し、両方とも INT_MIN（int型の最小値）で初期化します。
• リストを走査し、各ノードに対して次の判定を行います。
  • ノードの値が first_max より大きい場合：現在の first_max を second_max へ退避させ、first_max をその値で更新します。
  • それ以外で、ノードの値が second_max より大きい場合：second_max をその値で更新します。
• 走査が完了した時点の second_max が、リスト内で2番目に大きい要素です。

C++による実装例

以下のコードでは、新しいノードを先頭に追加する prepend() 関数でリストを構築し、secondLargestElement() 関数で2番目に大きい値を求めています。

#include<iostream>
#include<climits>
using namespace std;
class Node {
    public:
        int data;
        Node *next;
};
// 先頭にノードを挿入する関数
void prepend(Node** start, int new_data) {
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = NULL;
    if ((*start) != NULL){
        new_node->next = (*start);
        *start = new_node;
    }
    (*start) = new_node;
}
// 2番目に大きい要素を返す関数
int secondLargestElement(Node *start) {
    int first_max = INT_MIN, second_max = INT_MIN;
    Node *p = start;
    while(p != NULL){
        if (p->data > first_max) {
            second_max = first_max;
            first_max = p->data;
        } else if (p->data > second_max)
            second_max = p->data;
        p = p->next;
    }
    return second_max;
}
int main() {
    Node* start = NULL;
    prepend(&start, 15);
    prepend(&start, 16);
    prepend(&start, 10);
    prepend(&start, 9);
    prepend(&start, 7);
    prepend(&start, 17);
    cout << "Second largest element is: " << secondLargestElement(start);
}

出力結果

上記のプログラムでは、挿入順の関係でリストは [17, 7, 9, 10, 16, 15] として構築されます。最大値は17なので、2番目に大きい値は16となり、実行すると次のように表示されます。

Second largest element is: 16

まとめ

連結リストから2番目に大きい要素を探す場合は、リストを1回の走査で済ませながら、最大値と2番目の値を同時に追跡するのが最も効率的です。重複した値の扱いや、要素が2個未満の場合（2番目に大きい値が存在しないケース）のエラー処理を実装に加えておくと、より堅牢なプログラムになります。