এই সমস্যায়, আমাদের ডান এবং নিচে দুটি পয়েন্টার নোডের সমন্বয়ে লিঙ্কযুক্ত তালিকা দেওয়া হয়েছে।
-
ডান নোড প্রধান লিঙ্কযুক্ত তালিকা পয়েন্টার।
-
ডাউন নোড সেই নোড দিয়ে শুরু হওয়া সেকেন্ডারি লিঙ্কড তালিকার জন্য।
সমস্ত লিঙ্কযুক্ত তালিকাগুলি সাজানো হয়েছে৷
৷আমাদের কাজ হল একটি লিঙ্ক করা তালিকাকে সমতল করার জন্য একটি প্রোগ্রাম তৈরি করা এবং ফলস্বরূপ তালিকাটি নিজেই একটি সাজানো হবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক
ইনপুট
আউটপুট
1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5
সমাধান পদ্ধতি
সমস্যার একটি সমাধান হল একটি লিঙ্ক করা তালিকার জন্য মার্জ সর্ট ব্যবহার করা . এই পদ্ধতি একটি সমতল তালিকা তৈরি করতে একটি সাজানো ক্রমে তালিকাগুলিকে পুনরাবৃত্তিমূলকভাবে একত্রিত করবে৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node *right, *down;
};
Node* head = NULL;
Node* mergeList(Node* a, Node* b){
if (a == NULL)
return b;
if (b == NULL)
return a;
Node* result;
if (a->data < b->data){
result = a;
result->down = mergeList(a->down, b);
}
else{
result = b;
result->down = mergeList(a, b->down);
}
result->right = NULL;
return result;
}
Node* flattenLinkedList(Node* root){
if (root == NULL || root->right == NULL)
return root;
root->right = flattenLinkedList(root->right);
root = mergeList(root, root->right);
return root;
}
Node* push(Node* head_ref, int data){
Node* new_node = new Node();
new_node->data = data;
new_node->right = NULL;
new_node->down = head_ref;
head_ref = new_node;
return head_ref;
}
int main(){
head = push(head, 7);
head = push(head, 1);
head->right = push(head->right, 11);
head->right = push(head->right, 5);
head->right = push(head->right, 4);
head->right->right = push(head->right->right, 12);
head->right->right = push(head->right->right, 6);
head->right->right->right = push(head->right->right->right, 8);
head->right->right->right->right = push(head->right->right->right->right, 16);
head = flattenLinkedList(head);
cout<<"The Flattened Linked list is : \n";
Node* temp = head;
while (temp != NULL){
cout<<temp->data<<" => ";
temp = temp->down;
}
cout<<"NULL";
return 0;
} আউটপুট
The Flattened Linked list is : 1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL
