हमें एक लिंक्ड लिस्ट दी गई है। लिस्ट पहले सॉर्ट की गई है और फिर K नोड्स द्वारा रोटेट की गई है। लक्ष्य K का मान ज्ञात करना है। यदि हमें नीचे दी गई लिंक्ड लिस्ट इनपुट के रूप में दी गई है जो K नोड्स द्वारा रोटेटेड है:
तो मूल लिस्ट रही होगी:
और हम यहाँ देख सकते हैं K=2 है। इनपुट लिंक्ड लिस्ट मूल सॉर्टेड लिंक्ड लिस्ट का 2 नोड्स का रोटेशन है।
उदाहरण सहित समझ
इनपुट - लिस्ट: 5 → 7 → 9 → 1 → 3
आउटपुट
लिंक्ड लिस्ट में तत्व हैं: 5 7 9 1 3
सॉर्टेड और रोटेटेड लिंक्ड लिस्ट में रोटेशन की संख्या: 3
व्याख्या - हम मूल सॉर्टेड लिस्ट में तीन रोटेशन के बाद इनपुट लिस्ट प्राप्त कर सकते हैं।
1 → 3 → 5 → 7 → 9, मूल 9 → 1 → 3 → 5 → 7, रोटेशन 1 7 → 9 → 1 → 3 → 5, रोटेशन 2 5 → 7 → 9 → 1 → 3, रोटेशन 3
इनपुट - लिस्ट: 17 → 25 → 62 → 99
आउटपुट
लिंक्ड लिस्ट में तत्व हैं: 17 25 62 99
सॉर्टेड और रोटेटेड लिंक्ड लिस्ट में रोटेशन की संख्या: 4
व्याख्या - हम मूल सॉर्टेड लिस्ट में चार रोटेशन के बाद इनपुट लिस्ट प्राप्त कर सकते हैं।
17 → 25 → 62 → 99, मूल 99 → 17 → 25 → 62, रोटेशन 1 62 → 99 → 17 → 25, रोटेशन 2 25 → 62 → 99 → 17, रोटेशन 3 17 → 25 → 62 → 99, रोटेशन 4
प्रोग्राम में उपयोग किया गया दृष्टिकोण
इनपुट लिंक्ड लिस्ट में एक बिंदु होगा जहां अगला नोड पिछले से छोटा होगा। यदि इनपुट स्ट्रिंग भी सॉर्टेड है तो यह मूल का पूर्ण-रोटेशन है। हेड नोड से शुरू करके, तब तक ट्रैवर्स करें जब तक (वर्तमान नोड का डेटा > हेड नोड का डेटा) और काउंट बढ़ाएँ। उस मामले में जहां (वर्तमान नोड का डेटा < हेड नोड का डेटा) लूप तोड़ें। काउंट में मूल लिस्ट में किए गए रोटेशन की संख्या होगी जिससे इनपुट लिस्ट प्राप्त होती है।
- एक इनपुट लिस्ट लें और उसमें तत्व डालें।
- फंक्शन
insert_node(struct List_Node** head, int data)डेटा के साथ सिंगली लिंक्ड लिस्ट के हेड पर नोड्स डालता है। - फंक्शन
print(struct List_Node* node)हेड से अंत तक व्हाइल लूप का उपयोग करके इनपुट लिंक्ड लिस्ट प्रिंट करता है। - फंक्शन
rotations(struct List_Node* head)लिंक्ड लिस्ट के हेड पॉइंटर को लेता है और मूल लिंक्ड लिस्ट में किए गए रोटेशन की संख्या लौटाता है जिससे इनपुट लिंक्ड लिस्ट प्राप्त होती है। - प्रारंभिक काउंट 0 लें।
- हेड नोड के डेटा भाग को अस्थायी चर के रूप में लें।
- व्हाइल लूप का उपयोग करके, लिंक्ड लिस्ट के अंत तक ट्रैवर्स करें (head != NULL)।
- यदि प्रत्येक वर्तमान नोड का डेटा temp से बड़ा है तो काउंट बढ़ाएँ।
- यदि वर्तमान नोड का डेटा हेड नोड के डेटा (temp) से कम है। ब्रेक करें।
- हम रोटेशन की संख्या गिनेंगे।
- परिणाम के रूप में काउंट लौटाएँ।
उदाहरण
#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
