C++でソートおよびローテーションされたリンクリストのローテーションをカウントします

リンクリストが表示されます。リストは最初にソートされ、次にK個のノードでローテーションされます。目標は、Kの値を見つけることです。K個のノードだけ回転する入力としてリンクリストを以下に示す場合-

それならオリジナルは-

ここでKは2であることがわかります。入力リンクリストは、元のソートされたリンクリストの2ノードのローテーションです。

例を挙げて理解しましょう。

入力 −リスト：5→7→9→1→3

出力

リンクリストの要素は次のとおりです。5791 3

ソートおよびローテーションされたリンクリストのローテーション数は-3

説明 −元のソート済みリストで3回転した後、入力リストを取得できます。

1 → 3 → 5 → 7 → 9, original
9 → 1 → 3 → 5 → 7, rotation 1
7 → 9 → 1 → 3 → 5, rotation 2
5 → 7 → 9 → 1 → 3 rotation 3

入力 −リスト−17→25→62→99

出力

リンクリストの要素は− 17 25 62 99

ソートおよびローテーションされたリンクリストのローテーション数は-4

説明 −元のソート済みリストで4回転した後、入力リストを取得できます。

17 → 25 → 62 → 99, original
99 → 17 → 25 → 62, rotation 1
62 → 99 → 17 → 25, rotation 2
25 → 62 → 99 → 17, rotation 3
17 → 25 → 62 → 99, rotation 4

以下のプログラムで使用されているアプローチは次のとおりです

入力リンクリストには、次のノードが前のノードよりも小さい1つのポイントがあります。入力文字列も並べ替えられている場合は、元の文字列が完全に回転しています。ヘッドノードから開始して、（現在のノードのデータ>ヘッドノードのデータ）までトラバースし、カウントをインクリメントします。 （現在のノードのデータ<ヘッドノードのデータ）がループを中断する場合。カウントには、入力リストを取得するための元のリストのローテーション数が含まれます。

• 入力リストを取得し、その中に要素を挿入します。

• 関数insert_node（struct List_Node ** head、int data）は、データを含む単一リンクリストの先頭にノードを挿入します。

• 関数print（struct List_Node * node）は、whileループを使用して、入力リンクリストを先頭から最後まで出力します。

• 関数rotations（struct List_Node * head）は、リンクリストのヘッドポインターを取得し、元のリンクリストで実行された回転数を返し、入力リンクリストを取得します。

• 初期カウントを0とします。

• 一時変数をヘッドノードのデータ部分として使用します。

• whileループを使用して、リンクリストの最後に到達するまでトラバースします。 （head！=NULL）。

• 現在のすべてのノードのデータが一時よりも大きい場合のインクリメントカウント。

• 現在のノードのデータがヘッドノードのデータ（一時）よりも少ない場合。休憩、

• 回転数を数​​えます。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
struct List_Node{
   int data;
   struct List_Node* next;
};
int rotations(struct List_Node* head){
   int count = 0;
   int temp = head->data;
   while (head != NULL){
      if (temp > head->data){
         break;
      }
      count++;
      head = head->next;
   }
   return count;
}
void insert_node(struct List_Node** head, int data){
   struct List_Node* new_node = new List_Node;
   new_node->data = data;
   new_node->next = (*head);
   (*head) = new_node;
}
void print(struct List_Node* node){
   while (node != NULL){
      cout<<node->data<<" ";
      node = node->next;
   }
}
int main(){
   struct List_Node* head = NULL;
   insert_node(&head, 2);
   insert_node(&head, 1);
   insert_node(&head, 18);
   insert_node(&head, 35);
   insert_node(&head, 28);
   cout<<"Elements in the linked list are: ";
   print(head);
   cout<<"\nCount of rotations in sorted and rotated linked list are: "<<rotations(head);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Elements in the linked list are: 28 35 18 1 2
Count of rotations in sorted and rotated linked list are: 2