C++の単一の循環リンクリストで最小要素と最大要素を検索します

ここでは、1つの単一循環リンク線形リストから最小値と最大値を取得する方法を説明します。基本的な考え方はとてもシンプルです。最後のノードの次の部分は最初のノードを指し、最初のノードも開始ポインターを使用して指します。リストに要素を挿入すると、新しく挿入されたノードの次の部分が挿入された後、開始ノードのアドレスで更新されます。

最初に、minには正の無限大が割り当てられ、maxには負の無限大が割り当てられます。次に、リストを左から右にトラバースします。現在の要素がmin要素よりも小さい場合は、minを更新し、現在の要素がmax要素よりも大きい場合は、maxを更新します。したがって、最小値と最大値を取得できます。

例

#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;
   while (current->next != *start) {
      if (current->data < min) {
         min = current->data;
      }
      if (current->data > max) {
         max = current->data;
      }
      current = current->next;
   }
   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);
}

出力

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