The list isn’t terminating with null.
Please check out what’s the problem.
#include
using namespace std;
// Program to make a linked list with following manipulation options:
// 1. Merging two lists using Mergesort kind of approach.
// 2. Merging two lists using Recursive approach.
class node{
public:
int data;
node* next;
node(int val){
data = val;
next = NULL;
}
};
class LinkedList{
private:
node* head;
public:
// constructor
LinkedList(){
head = NULL;
}
// Destructor to delete all the dynamically memory allocated nodes in list.
~LinkedList(){
while(head != NULL){
node* save = head->next;
delete head;
head = save;
}
}
// Returns the node at Head
node getHeadNode(){
return *head;
}
// Returns head
node* getHead(){
return head;
}
// Prints the list
void printList(){
cout<<"Printing list: \n";
node* temp = head;
while(temp != NULL){
cout<<temp->data<<" -> ";
temp = temp->next;
}
cout<<"END\n";
}
void insertAtHead(int temp){
node* newNode = new node(temp);
if(head==NULL){
head = newNode;
} else{
node* save = head;
head = newNode;
newNode->next = save;
}
}
// creates a list by inserting at head
void createLinkList(){
bool flag = true;
cout<<"Enter integer to be inserted in list ( Enter -1 to terminate list building ) : \n";
while(flag){
int temp;
cin>>temp;
if(temp != -1){
insertAtHead(temp);
} else{
// Terminating list building
flag = false;
}
}
printList();
}
};
node* mergeLists(node* h1, node* h2){
node* head=NULL;
node* tail=NULL;
if( (h1->data) <= (h2->data) ){ // Deciding the head
head = h1;
tail = h1;
h1 = h1->next;
} else{
head = h2;
tail = h2;
h2 = h2->next;
}
while(h2 != NULL && h1 != NULL){ //setting links in ascending order of data comparing both lists
if( (h1->data) <= (h2->data) ){
tail->next = h1;
h1 = h1->next;
} else{
tail->next = h2;
h2 = h2->next;
}
tail = tail->next;
}
while(h1 != NULL){ // Setting(copying) links into list1 if not reached to null yet
tail->next = h1;
h1 = h1->next;
tail = tail->next;
}
while(h2 != NULL){ // Setting(copying) links into list2 if not reached to null yet
tail->next = h2;
h2 = h2->next;
tail = tail->next;
}
return head;
}
void printUsingHead(node* temp){
while(temp != NULL){
temp = temp->next;
}
cout<<“END”<<endl;
}
node* mergeListsRecursively(node* h1, node* h2){
//
// cout<data<<" "<data<<endl;
// system(“pause”);
//
if(h1 == NULL){
return h2;
} else if(h2 == NULL){
return h1;
}
node* head;
if(h1->data < h2->data){
head = h1;
head->next = mergeListsRecursively(h1->next, h2);
} else{
head = h2;
head->next = mergeListsRecursively(h1, h2->next);
}
return head;
}
int main(){
LinkedList list1, list2;
list1.createLinkList();
list2.createLinkList();
cout<<“Using mergesort like iterative approach : \n”;
node* mergedListHead = mergeLists(list1.getHead(), list2.getHead());
printUsingHead(mergedListHead);
cout<<“Using recursive approach : \n”;
node* mergedListHead2 = mergeListsRecursively(list1.getHead(), list2.getHead());
printUsingHead(mergedListHead2);
}