इस ट्यूटोरियल में एक लिंक की गई सूची को देखते हुए, और हमें सूची की शुरुआत में सभी संख्याओं को 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++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।