সমস্যা বিবরণ
একটি লিংকড লিস্ট দেওয়া আছে যাতে প্রতিটি নোডে right (মেইন লিস্ট) এবং down (সাব-লিস্ট) পয়েন্টার রয়েছে। সকল লিস্ট সর্টেড। আমাদের কাজ হল লিংকড লিস্টকে ফ্ল্যাটেন করে একটি সর্টেড লিস্ট বানানো।
উদাহরণ
ইনপুট: (চিত্র)
আউটপুট: 1 → 4 → 5 → 6 → 7 → 8 → 11 → 12 → 16 → NULL
সমাধানের পদ্ধতি
মার্জ সোর্ট ব্যবহার করে রিকার্সিভলি সাব-লিস্টগুলো মার্জ করে একটি সর্টেড ফ্ল্যাটেন্ড লিস্ট তৈরি করা।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *right, *down;
};
Node* mergeList(Node* a, Node* b) {
if (!a) return b;
if (!b) 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 || !root->right) return root;
root->right = flattenLinkedList(root->right);
return mergeList(root, root->right);
}
// helper functions: push, main driver omitted for brevity
আউটপুট
The Flattened Linked list is : 1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL
