একটি লিঙ্ক করা তালিকা হল একটি রৈখিক ডেটা কাঠামো যা উপাদানগুলিকে সঞ্চয় করে এবং পরবর্তী ডেটা নোডে একটি পয়েন্টারও সঞ্চয় করে৷
লিঙ্কযুক্ত তালিকার সাজানোর ক্ষেত্রে এই সমস্যায়, বিকল্প সাজানোর অর্থ এমনভাবে সাজানো যাতে ১ম নোডে ন্যূনতম মান সহ ডেটা থাকে, ২য় নোডে সর্বোচ্চ মান সহ ডেটা থাকে, তৃতীয়টি পরের সর্বনিম্ন (দ্বিতীয় ন্যূনতম মান) সহ এবং তাই বিকল্প ম্যাক্সিমা এবং মিনিমাসের এই প্যাটার্নটি লিঙ্ক করা তালিকার বিকল্প সাজানোর মাধ্যমে তৈরি করা হয়েছে।
সমস্যাটি আরও ভালোভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
Input : 3 > 4 > 21 >67 > 1 > 8. Output : 1 > 67 > 3 > 21 > 4 > 8. Explanation : Sort order of elements is 1 , 3 , 4 ,8 ,21 ,67. For required output we need to take one value from the beginning and one from end and it outputs the result.
এখন, আমরা সমস্যা সম্পর্কে জানি। আমরা এই সমস্যার সমাধান খুঁজে বের করার চেষ্টা করব। সুতরাং, এখন যেহেতু আমাদের মিনিমাম এবং ম্যাক্সিমা বিকল্প করতে হবে আমাদের সেই অনুযায়ী লিঙ্ক করা তালিকাগুলিকে সাজাতে হবে। এই জন্য, যে কোন লিঙ্ক তালিকা বাছাই ব্যবহার করা যেতে পারে. তারপর আমরা শুরু থেকে একটি এবং শেষ থেকে একটি মান নেব। ওভারল্যাপিং এড়াতে দুটি ভিন্ন তালিকা ব্যবহার করা ভাল। আমরা দুটি অর্ধের শেষের অংশটিকে বিপরীত করব এবং তারপরে তাদের বিকল্প ক্রমে আবার মার্জ করব। যেহেতু আমাদের মার্জ সাজানোর কৌশলের কিছু অংশ ব্যবহার করতে হবে, তাই সাজানোর জন্যও মার্জ সাজানো বেশ কার্যকর।
অ্যালগরিদম
Step 1 : Sort the linked list using merge sort technique. Step 2 : Create two linked list of half the length of the original linked list. Now, place one half in first half linked list and other half in second half linked list. Step 3 : reverse the second linked list and store in new linked list (required for reversal ). Step 4 : Create the result linked list using the first and reverse linked list. Using the elements of both list in alternate order.
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
Node* getNode(int data){
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) ;
Node* SortedMerge(Node* a, Node* b) ;
void MergeSort(Node** headRef) ;
void alternateMerge(Node* head1, Node* head2) ;
Node* altSortLinkedList(Node* head) ;
void printList(Node* head) ;
static void reverse(Node** head_ref){
Node* prev = NULL;
Node* current = *head_ref;
Node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
int main(){
Node* head = getNode(3);
head->next = getNode(4);
head->next->next = getNode(21);
head->next->next->next = getNode(67);
head->next->next->next->next = getNode(1);
head->next->next->next->next->next = getNode(8);
cout << "Initial list: ";
printList(head);
head = altSortLinkedList(head);
cout << "\nSorted list: ";
printList(head);
return 0;
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef){
Node* fast;
Node* slow;
if (source == NULL || source->next == NULL) {
*frontRef = source;
*backRef = NULL;
}
else {
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
Node* SortedMerge(Node* a, Node* b){
Node* result = NULL;
if (a == NULL)
return b;
else if (b == NULL)
return a;
if (a->data <= b->data) {
result = a;
result->next = SortedMerge(a->next, b);
} else {
result = b;
result->next = SortedMerge(a, b->next);
}
return result;
}
void MergeSort(Node** headRef){
Node* head = *headRef;
Node *a, *b;
if ((head == NULL) || (head->next == NULL))
return;
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
void alternateMerge(Node* head1, Node* head2){
Node *p, *q;
while (head1 != NULL && head2 != NULL) {
p = head1->next;
head1->next = head2;
head1 = p;
q = head2->next;
head2->next = head1;
head2 = q;
}
}
Node* altSortLinkedList(Node* head){
MergeSort(&head);
Node *front, *back;
FrontBackSplit(head, &front, &back);
reverse(&back);
alternateMerge(front, back);
return front;
}
void printList(Node* head){
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
} আউটপুট
Initial list: 3 4 21 67 1 8 Sorted list: 1 67 3 21 4 8
