C++ ব্যবহার করে সিঙ্গলি লিংকড লিস্টে মার্জ সর্ট

সমস্যা বিবরণ

একটি লিংকড লিস্ট দেওয়া আছে। মার্জ সর্ট অ্যালগরিদম ব্যবহার করে সেটি সর্ট করুন।

List: 10→20→8→17→5→13→4
Sorted list: 4→5→8→10→13→17→20

এলগরিদম

1. যদি হেড NULL হয় বা লিস্টে শুধু একটি এলিমেন্ট থাকে তবে লিস্ট রিটার্ন করুন
2. মূল লিস্টকে ২ অংশে ভাগ করে দুটি লিস্ট তৈরি করুন
3. প্রথম ও দ্বিতীয় অংশকে আলাদাভাবে সর্ট করুন
4. দুটি সর্টেড লিস্ট মার্জ করুন

উদাহরণ কোড

#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;
}

void splitList(node *src, node **fRef, node **bRef) {
    node *fast;
    node *slow;
    slow = src;
    fast = src->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *fRef = src;
    *bRef = slow->next;
    slow->next = NULL;
}

void mergeSort(node **head) {
    node *p = *head;
    node *a = NULL;
    node *b = NULL;
    if (p == NULL || p->next == NULL) {
        return;
    }
    splitList(p, &a, &b);
    mergeSort(&a);
    mergeSort(&b);
    *head = mergeSortedLists(a, b);
}

int main() {
    int arr[] = {10, 20, 8, 17, 5, 13, 4};
    node *head;
    head = createList(arr, SIZE(arr));
    cout << "Unsorted list: " << endl;
    displayList(head);
    mergeSort(&head);
    cout << "Final sorted list: " << endl;
    displayList(head);
    return 0;
}

আউটপুট

প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:

Unsorted list: 10 20 8 17 5 13 4
Final sorted list: 4 5 8 10 13 17 20