C++で双方向連結リストの最大ノードを検索する方法

この問題では、双方向連結リスト（Doubly Linked List）LLが与えられ、リスト内の最大のノードを見つけることが課題となります。

問題の例

具体例を使って問題を理解しましょう。

入力 : linked-list = 5 -> 2 -> 9 -> 8 -> 1 -> 3
出力 : 9

解法アプローチ

この問題に対するシンプルな解決策は、連結リストを先頭から末尾まで線形に走査することです。走査の過程で、現在のノードのデータ値がこれまでの最大値（maxVal）よりも大きい場合、maxValを現在のノードに更新します。

走査が完了した時点で、maxValが指すノードのデータがリスト全体の最大値となるため、その値を返します。

アルゴリズムの手順

1. maxValとcurrの両方をヘッドノードで初期化します。
2. currがNULLになるまで、リストを順次走査します。
3. 各ステップで、curr->dataがmaxVal->dataより大きければ、maxVal = curr とします。
4. currを次のノードへ進めます。
5. 走査終了後、maxVal->data を返します。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
struct Node{
    int data;
    struct Node* next;
    struct Node* prev;
};
void push(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
    (*head_ref) = new_node;
}
int findLargestNodeInDLL(struct Node** head_ref){
   struct Node *maxVal, *curr;
   maxVal = curr = *head_ref;
   while (curr != NULL){
      if (curr->data > maxVal->data)
         maxVal = curr;
      curr = curr->next;
   }
   return maxVal->data;
}
int main(){
   struct Node* head = NULL;
   push(&head, 5);
   push(&head, 2);
   push(&head, 9);
   push(&head, 1);
   push(&head, 3);
   cout<<"双方向連結リストの最大ノードは "<<findLargestNodeInDLL(&head);
   return 0;
}

出力結果

双方向連結リストの最大ノードは 9

計算量について

このアルゴリズムは、リスト内のすべてのノードを一度だけ訪問するため、時間計算量は O(n) となります。ここで n は連結リストのノード数です。また、追加の補助変数として2つのポインタのみを使用するため、空間計算量は O(1) です。