#include<iostream>
using namespace std;
struct List{
int data;
List * next;
};
void sortedInsert(List** head, List* newNode)
{
List* currentNode;
if (*head == NULL|| (*head)->data>= newNode->data) {
newNode->next = *head;
*head = newNode;
}
else {
currentNode = *head;
while (currentNode->next != NULL
&& currentNode->next->data
< newNode->data) {
currentNode = currentNode->next;
}
newNode->next = currentNode->next;
currentNode->next = newNode;
}
}
List* newNode(int data)
{
List* node = new List();
node->data = data;
node->next = NULL;
return node;
}
void displayList(struct List * node){
while(node != NULL){
cout<<node->data<<" ";
node = node->next;
}
}
void printLists(List* node)
{
if (node == NULL)
return;
printLists(node->next);
cout << node->data << " ";
}
void merge(struct List * list1, struct List * list2){
struct List *list3 = NULL;
while(list1 !=NULL){
int item = list1->data;
List * new_node = newNode(item);
sortedInsert(&list3, new_node);
list1= list1->next;
}
while(list2 !=NULL){
int item = list2->data;
List * new_node = newNode(item);
sortedInsert(&list3, new_node);
list2= list2->next;
}
printLists(list3);
}
int main(){
struct List * list1 = NULL;
List * node = newNode(1);
sortedInsert(&list1, node);
node = newNode(3);
sortedInsert(&list1,node);
node = newNode(5);
sortedInsert(&list1, node);
node = newNode(6);
sortedInsert(&list1, node);
cout<<"List 1 contains\n";
displayList(list1);
struct List * list2 = NULL;
node = newNode(2);
sortedInsert(&list2,node);
node = newNode(4);
sortedInsert(&list2, node);
node = newNode(8);
sortedInsert(&list2, node);
node = newNode(9);
sortedInsert(&list2, node);
cout<<"\nList 2 contains\n";
displayList(list2);
cout<<"\nList 3 contains\n";
merge(list1, list2);
}
Comments
Leave a comment