আমাদের একটি লিংকড লিস্ট দেওয়া আছে। এই লিস্টটি প্রথমে সর্ট করা হয়েছে এবং তারপর K সংখ্যক নোড দ্বারা রোটেট করা হয়েছে। লক্ষ্য হলো K-এর মান বের করা।
যদি নিচের লিংকড লিস্ট ইনপুট হিসেবে দেওয়া থাকে যা K নোড দিয়ে রোটেট করা:
তাহলে মূল লিস্টটি অবশ্যই:
এখানে K = ২। ইনপুট লিস্টটি মূল সর্টেড লিস্টের ২ নোড রোটেশন।
উদাহরণ দিয়ে বুঝি
ইনপুট − List: 5 → 7 → 9 → 1 → 3
আউটপুট −
লিংকড লিস্টের উপাদান: 5 7 9 1 3
সর্টেড ও রোটেটেড লিংকড লিস্টে রোটেশনের সংখ্যা: ৩
ব্যাখ্যা − মূল সর্টেড লিস্ট থেকে তিনবার রোটেশন করলে ইনপুট লিস্ট পাওয়া যায়।
1 → 3 → 5 → 7 → 9, মূল 9 → 1 → 3 → 5 → 7, রোটেশন ১ 7 → 9 → 1 → 3 → 5, রোটেশন ২ 5 → 7 → 9 → 1 → 3, রোটেশন ৩
ইনপুট − List: 17 → 25 → 62 → 99
আউটপুট −
লিংকড লিস্টের উপাদান: 17 25 62 99
সর্টেড ও রোটেটেড লিংকড লিস্টে রোটেশনের সংখ্যা: ৪
ব্যাখ্যা − মূল সর্টেড লিস্ট থেকে চারবার রোটেশন করলে ইনপুট লিস্ট পাওয়া যায়।
17 → 25 → 62 → 99, মূল 99 → 17 → 25 → 62, রোটেশন ১ 62 → 99 → 17 → 25, রোটেশন ২ 25 → 62 → 99 → 17, রোটেশন ৩ 17 → 25 → 62 → 99, রোটেশন ৪
প্রোগ্রামে ব্যবহৃত পদ্ধতি
ইনপুট লিংকড লিস্টে একটি পয়েন্ট থাকবে যেখানে পরবর্তী নোডের মান বর্তমান নোডের মানের চেয়ে ছোট। যদি ইনপুট লিস্টও সর্টেড থাকে, তবে সেটি মূল লিস্টের পূর্ণ রোটেশন (full-rotation)। হেড নোড থেকে শুরু করে যতক্ষণ (বর্তমান নোডের ডেটা > হেড নোডের ডেটা) ততক্ষণ ঘুরুন এবং কাউন্ট বাড়ান। যেখানে (বর্তমান নোডের ডেটা < হেড নোডের ডেটা) সেখানে লুপ ব্রেক করুন। কাউন্টটিই হবে মূল লিস্ট থেকে ইনপুট লিস্ট পাওয়ার জন্য দরকার রোটেশনের সংখ্যা।
- ইনপুট লিস্ট নিন এবং উপাদান ইনসার্ট করুন।
insert_node(struct List_Node** head, int data)ফাংশন সিংলি লিংকড লিস্টের হেডে নোড ইনসার্ট করে।print(struct List_Node* node)ফাংশন হেড থেকে শেষ পর্যন্ত লিংকড লিস্ট প্রিন্ট করে।rotations(struct List_Node* head)ফাংশন হেড পয়েন্টার নিয়ে মূল লিস্ট থেকে ইনপুট লিস্ট পাওয়ার জন্য কতবার রোটেশন করা হয়েছে তা রিটার্ন করে।- প্রাথমিক কাউন্ট ০।
tempভেরিয়েবলে হেড নোডের ডেটা রাখুন।whileলুপে লিংকড লিস্টের শেষ পর্যন্ত (head!=NULL) ঘুরুন।- প্রতিটি বর্তমান নোডের ডেটা
temp-এর চেয়ে বড় হলে কাউন্ট বাড়ান। - যদি বর্তমান নোডের ডেটা হেড নোডের ডেটা (
temp)-এর চেয়ে ছোট হয়, ব্রেক করুন। - রোটেশনের সংখ্যা পাওয়া যাবে।
countরিটার্ন করুন।
উদাহরণ
#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
