#include
using namespace std;
class node
{
public:
int data;
node *next;
//Constructor
node(int d)
{
data = d;
next = NULL;
}
};
void insertAtHead(node *&head, int data)
{
node *n = new node(data);
n->next = head;
head = n;
}
void insertAtTail(node &head, int data)
{
if(head == NULL){
noden = new node(data);
head = n;
return;
}
node *temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
node *n = new node(data);
temp->next = n;
}
node mergeSortedLinkedList(nodehead, nodehead1){
nodenewHead = NULL;
while(head->next != NULL && head1->next != NULL){
if((head->data > head1->data) || (head->next == NULL)){
insertAtTail(newHead, head1->data);
head1 = head1->next;
}
else{
insertAtTail(newHead, head->data);
head = head->next;
}
}
return newHead;
}
void print(node *head)
{
node *temp = head;
while (temp != NULL)
{
cout << temp->data << ", ";
temp = temp->next;
}
cout << endl;
}
int main()
{
node *head = NULL;
insertAtHead(head, 10);
insertAtHead(head, 8);
insertAtHead(head, 6);
insertAtHead(head, 2);
node *head1 = NULL;
insertAtHead(head, 9);
insertAtHead(head, 7);
insertAtHead(head, 3);
insertAtHead(head, 1);
print(head);
print(head1);
node*mergeHead = mergeSortedLinkedList(head, head1);
print(mergeHead);
return 0;
}