C++で連結リストのピーク要素を見つけるアルゴリズムを解説

このチュートリアルでは、C++を使って与えられた連結リスト（リンクリスト）からピーク要素を見つけるプログラムを作成します。

ピーク要素とは、両隣の要素（前後の要素）よりも大きい値を持つ要素のことです。それでは、問題を解くための手順を順番に見ていきましょう。

アルゴリズムの手順

• 連結リスト用のノード構造体（struct Node）を定義します。

• ダミーデータを使って連結リストを構築します。

• 連結リストが空、または要素数が1の場合など、ベースケース（境界条件）を先にチェックします。

• 最初の要素の値を変数 prev（前の要素）として保存しておきます。

• 連結リストを先頭から走査します。

  • 現在の要素が、前の要素と次の要素のどちらよりも大きいかどうかを判定します。

  • 条件を満たしていれば、その値をピーク要素として返します。

  • 条件を満たさない場合は、prev を現在の要素の値で更新して次へ進みます。

• 最後に結果を出力します。

なお、リストの末尾は「次の要素」が存在しないため、ループ終了後に末尾の要素とその前の要素を比較し、末尾が大きければそれもピーク要素となります。すべてのチェックで該当する要素が見つからなかった場合は -1 を返す仕様にしています。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void insertNewNode(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 findPeakElement(struct Node* head) {
   if (head == NULL) {
      return -1;
   }
   if (head->next == NULL) {
      return head->data;
   }
   int prev = head->data;
   Node *current_node;
   for (current_node = head->next; current_node->next != NULL; current_node = current_node->next) {
      if (current_node->data > current_node->next->data && current_node->data > prev) {
         return current_node->data;
      }
      prev = current_node->data;
   }
   if (current_node->data > prev) {
      return current_node->data;
   }
   return -1;
}
int main() {
   struct Node* head = NULL;
   insertNewNode(&head, 7);
   insertNewNode(&head, 4);
   insertNewNode(&head, 5);
   insertNewNode(&head, 2);
   insertNewNode(&head, 3);
   cout << findPeakElement(head) << endl;
   return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

5

コードの解説

この例では、連結リストは 3 → 2 → 5 → 4 → 7 の順で構成されています。走査を進めると、値 5 が前の要素 2 および次の要素 4 のどちらよりも大きいため、5 が最初に見つかったピーク要素として返されます。

計算量についても触れておくと、リストを一度だけ走査するため時間計算量は O(n)、補助的なメモリ使用量は O(1) となり、非常に効率的なアルゴリズムです。

まとめ

このチュートリアルでは、C++における連結リストからピーク要素を見つける方法を学びました。ベースケースの処理やリスト末尾の扱いなど、実装時の注意点も押さえておくことで、より堅牢なコードになります。

本チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。