सी ++ में क्रमबद्ध और घुमाए गए लिंक्ड सूची में घूर्णन की गणना करें

हमें एक लिंक्ड लिस्ट दी गई है। सूची को पहले क्रमबद्ध किया जाता है और फिर K संख्या के नोड्स द्वारा घुमाया जाता है। लक्ष्य K का मान ज्ञात करना है। यदि हमें इनपुट के रूप में लिंक की गई सूची नीचे दी गई है, जिसे K नोड्स की संख्या द्वारा घुमाया जाता है -

तब मूल अवश्य रहा होगा -

और हम देख सकते हैं K यहाँ 2 है। इनपुट लिंक्ड सूची मूल क्रमबद्ध लिंक्ड सूची में 2 नोड्स का रोटेशन है।

आइए उदाहरणों से समझते हैं।

इनपुट - सूची :5 → 7 → 9 → 1 → 3

आउटपुट

लिंक की गई सूची में तत्व हैं:5 7 9 1 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

स्पष्टीकरण - हम मूल क्रमबद्ध सूची में चार घुमावों के बाद इनपुट सूची प्राप्त कर सकते हैं।

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

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

इनपुट लिंक्ड सूची में एक बिंदु होगा जिस पर अगला नोड पिछले एक से छोटा होगा। यदि इनपुट स्ट्रिंग को भी सॉर्ट किया जाता है तो यह मूल स्ट्रिंग का पूर्ण-रोटेशन है। हेड नोड से शुरू होकर (वर्तमान नोड का डेटा> हेड नोड का डेटा) और इंक्रीमेंट काउंट तक ट्रैवर्स करें। मामले में जहां (वर्तमान नोड का डेटा <हेड नोड का डेटा) लूप को तोड़ता है। इनपुट सूची प्राप्त करने के लिए गणना में मूल सूची में कई घुमाव होंगे।

• एक इनपुट सूची लें और उसमें तत्व डालें।

• फ़ंक्शन इन्सर्ट_नोड (स्ट्रक्चर लिस्ट_नोड ** हेड, इंट डेटा) डेटा के साथ सिंगल-लिंक्ड सूचियों के शीर्ष पर नोड्स सम्मिलित करता है।

• फ़ंक्शन प्रिंट (स्ट्रक्चर लिस्ट_नोड * नोड) लूप का उपयोग करते हुए सिर से अंत तक इनपुट लिंक्ड सूची को प्रिंट करता है।

• फंक्शन रोटेशन (स्ट्रक्चर लिस्ट_नोड * हेड) लिंक्ड लिस्ट के हेड पॉइंटर को लेते हैं और इनपुट लिंक्ड लिस्ट प्राप्त करने के लिए मूल लिंक्ड लिस्ट में किए गए रोटेशन की गिनती लौटाते हैं।

• प्रारंभिक गणना 0 के रूप में लें।

• अस्थायी चर को हेड नोड के डेटा भाग के रूप में लें।

• लूप का उपयोग करते हुए, लिंक की गई सूची के अंत तक ट्रैवर्स तक पहुँच जाता है। (सिर!=नल)।

• हर मौजूदा नोड के डेटा के तापमान से ज़्यादा होने की स्थिति में इंक्रीमेंट काउंट.

• यदि वर्तमान नोड का डेटा हेड नोड के डेटा (अस्थायी) से कम है। ब्रेक,

• हम घुमावों की संख्या की गणना करेंगे।

• परिणाम के रूप में वापसी की गिनती।

उदाहरण

#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