Merge two Linked List In c without using inbuilt sort method-CodePudding

You are given two linked lists the thing is that one of them is sorted and the other isn't the task is that you have to merge them and sort their value while comparing during execution not sorting both linked lists separately and also without using any inbuilt method from c template library.

I have attempted the question by myself but it isn't working. I think it is approaching an infinite loop condition in the if condition!

This is what I have done:

#include <iostream>

using namespace std;
struct Student {
    int id;
    Student *next = NULL;
};
Student *first = NULL;
Student *last = NULL;
Student *first2 = NULL;
Student *last2 = NULL;

void display(Student *k);

void insert_end(Student *k);

void merge();

int main() {
    int exit = 1;
    do {
        cout << "11.Display, 12.Insert, 3.Merge\n";
        cout << "21.Display, 22.Insert, 0:exit\n";
        cin >> exit;
        switch (exit) {
            case 11:
                display(first);
                break;
            case 12:
                insert_end(last);
                break;
            case 3:
                // first = mergeTwoLists(first, first2);
                //merge();
                Student* SortedMerge(Student* a, Student* b);
                break;
            case 21:
                display(first2);
                break;
            case 22:
                insert_end(last2);
                break;
            default:
                cout << "WRONG\n";
                break;
        }
    } while (exit != 0);
    return 0;
}

void display(Student *k) {
    Student *p = k;
    while (p != NULL) {
        cout << "ID: " << p->id << "\n";
        p = p->next;
    }
}

void insert_end(Student *k) {
    cout << "This is the function of insert_end \n";
    Student *current = new Student;
    cout << "Enter ID: ";
    cin >> current->id;
    if (k == NULL) {
        if (k == last) {
            first = last = current;
        } else {
            first2 = last2 = current;
        }
    } else {
        if (k == last) {
            last->next = current;
            last = current;
        } else {
            last2->next = current;
            last2 = current;
        }
    }
}
void merge() {
    Student *p1 = first;
    Student *p2 = first2;
    while (p1 != NULL) {
        p2 = first2;
      while (p2->next != NULL) {
            if (p1->id <= p2->id) {
                Student *curr = p2;
                curr->next = p1->next;
                p1->next = curr;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}

What could be the possible optimized solution?

CodePudding user response：

You need at first to rewrite the function insert_end. Initially the both pointers last and last2 are null pointers

Student *first = NULL;
Student *last = NULL;
Student *first2 = NULL;
Student *last2 = NULL;

So if the user will decide at first to fill the second list then due to this if statement

if (k == NULL) {
    if (k == last) {
        first = last = current;
    } else {
        first2 = last2 = current;
    }
}

the function will insert a new node in the first list instead of the second list.

The function merge is also wrong. For starters it changes neither first nor first2 and neither last and last2.

If the if statement

if (p1->id <= p2->id) {
    Student *curr = p2;
    curr->next = p1->next;
    p1->next = curr;
}

gives the control then the data member next of the pointer p2 is changed due to these lines

    Student *curr = p2;
    curr->next = p1->next;

that is the data member next of the pointer of the second list points to the node of the first list.

But then after the if statement

p2 = p2->next;

the pointer p2 points to a node in the first list instead of pointing to a node in the second list.

To make the life easier you need to define one more structure as for example

struct List
{
    struct Student *first;
    struct Student *last;
};

and define the functions for pointers of this structure type.