লিংকড লিস্ট একটি লিনিয়ার ডেটা স্ট্রাকচার যা উপাদান সংরক্ষণ করে এবং পরবর্তী ডেটা নোডের পয়েন্টারও রাখে।
লিংকড লিস্ট সর্টিং সমস্যায় অল্টারনেট সর্ট মানে এমনভাবে সাজানো যেন ১ম নোডে ন্যূনতম মান, ২য় নোডে সর্বোচ্চ মান, ৩য় নোডে দ্বিতীয় ন্যূনতম মান - এইভাবে অল্টারনেট ম্যাক্সিমা ও মিনিমা প্যাটার্ন তৈরি হয়।
উদাহরণ দিয়ে বুঝি:
Input: 3 > 4 > 21 > 67 > 1 > 8 Output: 1 > 67 > 3 > 21 > 4 > 8 Explanation: সর্ট করা অর্ডার: 1, 3, 4, 8, 21, 67। প্রয়োজনীয় আউটপুটের জন্য শুরু থেকে একটি মান এবং শেষ থেকে একটি মান নিয়ে ফলাফল তৈরি করা হয়।
এখন সমাধান খুঁজি। যেহেতু অল্টারনেট মিনিমা-ম্যাক্সিমা चाहिये, তাই লিংকড লিস্টকে সেইমত সর্ট করতে হবে। যেকোনো লিংকড লিস্ট সর্টিং ব্যবহার করা যায়। তারপর শুরু থেকে একটি মান এবং শেষ থেকে একটি মান নিতে হবে। ওভারল্যাপ এড়াতে দুটি আলাদা লিস্ট ব্যবহার করা ভালো। দ্বিতীয় অর্ধেক রিভার্স করে আবার অল্টারনেট অর্ডারে মার্জ করুন। মার্জ সোর্ট টেকনিকের অংশ ব্যবহার করতে হলে সর্টিং-ও মার্জ সোর্ট দিয়ে করা দক্ষ।
আলগরিদম
Step 1: মার্জ সোর্ট টেকনিক দিয়ে লিংকড লিস্ট সর্ট করুন। Step 2: মূল লিংকড লিস্টের অর্ধেক দৈর্ঘ্যের দুটি লিংকড লিস্ট বানান। একে আধা রাখুন প্রথমে, বাকি আধা দ্বিতীয়তে। Step 3: দ্বিতীয় লিংকড লিস্ট রিভার্স করুন এবং নতুন লিংকড লিস্টে রাখুন (রিভার্সের জন্য প্রয়োজন)। Step 4: প্রথম এবং রিভার্সড লিংকড লিস্ট দিয়ে রেজাল্ট লিংকড লিস্ট বানান। দুটি লিস্টের উপাদান অল্টারনেট অর্ডারে ব্যবহার করুন।
C++ প্রোগ্রাম উদাহরণ
#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
