সমস্যা বিবরণ
দুটি সর্টেড সিঙ্গলি লিংকড লিস্ট দেওয়া আছে। এদের মার্জ করে একটি সর্টেড লিংকড লিস্ট বানানোর ফাংশন লিখুন।
List1: 10→15→17→20 List2: 5→9→13→19 Result: 5→9→10→13→15→17→19→20
এলগরিদম
1. দুটি লিস্ট ট্রাভার্স করুন
1.1. যদি list1->data < list2->data হয়
1.1.1. list1->data নতুন লিস্টে যোগ করুন এবং list1 পয়েন্টার বাড়ান
1.2. যদি list2->data < list1->data হয়
1.2.1. list2->data নতুন লিস্টে যোগ করুন এবং list2 পয়েন্টার বাড়ান
2. দুটি লিস্ট খালি না হওয়া পর্যন্ত প্রক্রিয়া চালিয়ে যান
3. ফলাফল লিস্ট রিটার্ন করুন
উদাহরণ কোড
#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct node {
int data;
struct node *next;
};
node *createList(int *arr, int n) {
node *head, *p;
p = head = new node;
head->data = arr[0];
head->next = NULL;
for (int i = 1; i < n; ++i) {
p->next = new node;
p = p->next;
p->data = arr[i];
p->next = NULL;
}
return head;
}
void displayList(node *head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
node *mergeSortedLists(node *head1, node *head2) {
node *result = NULL;
if (head1 == NULL) {
return head2;
}
if (head2 == NULL) {
return head1;
}
if (head1->data < head2->data) {
result = head1;
result->next = mergeSortedLists(head1->next, head2);
} else {
result = head2;
result->next = mergeSortedLists(head1, head2->next);
}
return result;
}
int main() {
int arr1[] = {10, 15, 17, 20};
int arr2[] = {5, 9, 13, 19};
node *head1, *head2, *result = NULL;
head1 = createList(arr1, SIZE(arr1));
head2 = createList(arr2, SIZE(arr1));
cout << "First sorted list: " << endl;
displayList(head1);
cout << "Second sorted list: " << endl;
displayList(head2);
result = mergeSortedLists(head1, head2);
cout << "Final sorted list: " << endl;
displayList(result);
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
First sorted list: 10 15 17 20 Second sorted list: 5 9 13 19 Final sorted list: 5 9 10 13 15 17 19 20
