C++ में दो सॉर्ट की गई लिंक्ड लिस्ट को मर्ज करना

समस्या कथन

दो सॉर्ट की गई सिंगली लिंक्ड लिस्ट दी गई हैं। दी गई दो सॉर्ट की गई लिंक्ड लिस्ट को मर्ज करने के लिए एक फ़ंक्शन लिखें।

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. परिणामी लिस्ट लौटाएं

C++ उदाहरण

#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) {
    if (!head1) return head2;
    if (!head2) return head1;
    Node *result = NULL;
    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(arr2));
    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