এই টিউটোরিয়ালে একটি লিঙ্ক করা তালিকা দেওয়া হয়েছে, এবং আমাদের তালিকার শুরুতে x-এর থেকে ছোট এবং পিছনে বাকিগুলো রাখতে হবে। আমাদের তাদের অর্ডার আগের মতোই ধরে রাখতে হবে। উদাহরণস্বরূপ
Input : 1->4->3->2->5->2->3, x = 3 Output: 1->2->2->3->3->4->5 Input : 1->4->2->10 x = 3 Output: 1->2->4->10 Input : 10->4->20->10->3 x = 3 Output: 3->10->4->20->10
এই সমস্যা সমাধানের জন্য, আমাদের এখন তিনটি লিঙ্কযুক্ত তালিকা তৈরি করতে হবে। যখন আমরা x এর চেয়ে ছোট একটি সংখ্যার সম্মুখীন হই, তখন আমরা এটিকে প্রথম তালিকায় সন্নিবেশ করি। এখন x এর সমান একটি মানের জন্য, আমরা এটিকে দ্বিতীয় স্থানে রাখি, এবং বৃহত্তর মানের জন্য, আমরা এটিকে এখন তৃতীয়টিতে সন্নিবেশ করি। শেষ পর্যন্ত, আমরা তালিকাগুলি একত্রিত করি এবং চূড়ান্ত তালিকা প্রিন্ট করি।
সমাধান খোঁজার পদ্ধতি
এই পদ্ধতিতে, আমরা তিনটি তালিকা বজায় রাখতে যাচ্ছি, যথা ছোট, সমান, বড়। এখন আমরা তাদের ক্রম বজায় রাখি এবং তালিকাগুলিকে একটি চূড়ান্ত তালিকায় সংযুক্ত করি, যা আমাদের উত্তর।
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure for our node
int data;
struct Node* next;
};
// A utility function to create a new node
Node *newNode(int data){
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
struct Node *partition(struct Node *head, int x){
struct Node *smallhead = NULL, *smalllast = NULL; // we take two pointers for the list //so that it will help us in concatenation
struct Node *largelast = NULL, *largehead = NULL;
struct Node *equalhead = NULL, *equallast = NULL;
while (head != NULL){ // traversing through the original list
if (head->data == x){ // for equal to x
if (equalhead == NULL)
equalhead = equallast = head;
else{
equallast->next = head;
equallast = equallast->next;
}
}
else if (head->data < x){ // for smaller than x
if (smallhead == NULL)
smalllast = smallhead = head;
else{
smalllast->next = head;
smalllast = head;
}
}
else{ // for larger than x
if (largehead == NULL)
largelast = largehead = head;
else{
largelast->next = head;
largelast = head;
}
}
head = head->next;
}
if (largelast != NULL) // largelast will point to null as it is our last list
largelast->next = NULL;
/**********Concatenating the lists**********/
if (smallhead == NULL){
if (equalhead == NULL)
return largehead;
equallast->next = largehead;
return equalhead;
}
if (equalhead == NULL){
smalllast->next = largehead;
return smallhead;
}
smalllast->next = equalhead;
equallast->next = largehead;
return smallhead;
}
void printList(struct Node *head){ // function for printing our list
struct Node *temp = head;
while (temp != NULL){
printf("%d ", temp->data);
temp = temp->next;
}
}
int main(){
struct Node* head = newNode(10);
head->next = newNode(4);
head->next->next = newNode(5);
head->next->next->next = newNode(30);
head->next->next->next->next = newNode(2);
head->next->next->next->next->next = newNode(50);
int x = 3;
head = partition(head, x);
printList(head);
return 0;
} আউটপুট
2 10 4 5 30
উপরের কোডের ব্যাখ্যা
উপরে বর্ণিত পদ্ধতিতে, আমরা ক্রমানুসারে বিষয়বস্তুর সাথে তিনটি লিঙ্কযুক্ত তালিকা রাখব। এই তিনটি লিঙ্কযুক্ত তালিকায় আলাদাভাবে x এর থেকে ছোট, সমান এবং বড় উপাদান থাকবে। আমাদের কাজ এখন সরলীকৃত হয়েছে. আমাদের তালিকাগুলিকে একত্রিত করতে হবে এবং তারপর মাথা ফেরত দিতে হবে৷
উপসংহার
এই টিউটোরিয়ালে, আমরা একটি প্রদত্ত মানের চারপাশে একটি লিঙ্কযুক্ত তালিকা বিভাজন এবং মূল ক্রম বজায় রাখার সমাধান করব। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
