Problem 1025-(Merge two ordered singly linked lists - Middle level) 1: Introduct
ID: 3742579 • Letter: P
Question
Problem 1025-(Merge two ordered singly linked lists - Middle level) 1: Introduction Problem description and (if any) background of the algorithms. Description ,, , , typedef int Elem Type; typedef struct LNode f Elem Type data; struct LNode next; LNode, LinkedList Merge two ordered singly linked lists with dumwy head nodes, and output the sum of all elements in the odd positions. Tips: insertion operation of linked lists Input: 110" , , , First line: two integers , n , m, and m, denoting number of elements in the wo linked lists respectively; Second line: m elements in the first linked list, one by one, by non-decreasing Third line: m elements in the second linked list, one by one, by non- decreasing order; Output: , After merging the two ordered singly linked lists to get First line: all elements in the new ordered singly linked list, one by one, in Second line: the sum of all elements in the odd-order modes in the new , linked list, output: non-decreasing order; new ordered singly ordered singly linked list. Sample Input 3 5 26 10 369 12 18 Sample Output 23669 10 12 18 29 2: Algorithm Specification Description (pseudo-code preferred) of all the algorithms involved for solving the problem, including specifications of main data structures. 3: Testing Results Table of test cases. Each test case usnally consists of a brief description of the purpose of this case, the expected result, the actual behavior of your program, the possible cause of a bug if your program does not function as expected, and the current statuspass", or "corrected". or "pending". 4: Analysis and Comments Analysis of the time and space complexities of the algorithms. Comments on further possible improvements.Explanation / Answer
#include<iostream>
using namespace std;
// Creating a NODE Structure
struct node
{
int data; // data
struct node *next; // link to next node and previous node
};
// Creating a class LIST
class list
{
struct node *start;
public:
void create(); // to create a list
void show(); // show
void merge(list,list); // Merge two list's
};
// Main function
int main()
{
list l1,l2,l3;
cout<<" Enter the First List in ascending order :: ";
l1.create(); // to create a first list
cout<<" Enter the Second List in ascending order :: ";
l2.create(); // to create a second list
cout<<" The first list is :: ";
l1.show();
cout<<" The second list is :: ";
l2.show();
l3.merge(l1,l2);
l3.show();
return 0;
}
// Functions
// Creating a new node
void list::create()
{
struct node *nxt_node,*pre_node;
int value,no,i;
start=nxt_node=pre_node=NULL;
cout<<" How many nodes :: ";
cin>>no;
cout<<" Enter "<<no<<" Elements :: ";
for(i=1;i<=no;i++)
{
cout<<" Enter [ "<<i<<" ] Element :: ";
cin>>value;
nxt_node=new node;
nxt_node->data=value;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
}
cout<<" The list is created! ";
}
// Displaying LIST
void list::show()
{
struct node *ptr=start;
cout<<" The List is :: ";
while(ptr!=NULL)
{
cout<<ptr->data<<" -> ";
ptr=ptr->next;
}
cout<<" ";
}
void list::merge(list l1,list l2)
{
struct node *nxt_node,*pre_node,*pptr,*qptr;
int dat;
pptr=l1.start;
qptr=l2.start;
start=nxt_node=pre_node=NULL;
while(pptr!=NULL && qptr!=NULL)
{
if(pptr->data<=qptr->data)
{
dat=pptr->data;
pptr=pptr->next;
}
else
{
dat=qptr->data;
qptr=qptr->next;
}
nxt_node=new node;
nxt_node->data=dat;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
}
if(pptr==NULL)
{
while(qptr!=NULL)
{
nxt_node=new node;
nxt_node->data=qptr->data;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
qptr=qptr->next;
}
}
else if(qptr==NULL)
{
while(pptr!=NULL)
{
nxt_node=new node;
nxt_node->data=pptr->data;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
pptr=pptr->next;
}
}
cout<<" The lists are merged....... ";
return;
}
OUTPUT
Enter the First List in ascending order ::
How many nodes :: 5
Enter 5 Elements ::
Enter [ 1 ] Element :: 1
Enter [ 2 ] Element :: 2
Enter [ 3 ] Element :: 3
Enter [ 4 ] Element :: 4
Enter [ 5 ] Element :: 5
The list is created!
Enter the Second List in ascending order ::
How many nodes :: 3
Enter 3 Elements ::
Enter [ 1 ] Element :: 1
Enter [ 2 ] Element :: 2
Enter [ 3 ] Element :: 3
The list is created!
The first list is ::
The List is :: 1 -> 2 -> 3 -> 4 -> 5 ->
The second list is ::
The List is :: 1 -> 2 -> 3 ->
The lists are merged.......
The List is :: 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 5 ->
#include<iostream>
using namespace std;
// Creating a NODE Structure
struct node
{
int data; // data
struct node *next; // link to next node and previous node
};
// Creating a class LIST
class list
{
struct node *start;
public:
void create(); // to create a list
void show(); // show
void merge(list,list); // Merge two list's
};
// Main function
int main()
{
list l1,l2,l3;
cout<<" Enter the First List in ascending order :: ";
l1.create(); // to create a first list
cout<<" Enter the Second List in ascending order :: ";
l2.create(); // to create a second list
cout<<" The first list is :: ";
l1.show();
cout<<" The second list is :: ";
l2.show();
l3.merge(l1,l2);
l3.show();
return 0;
}
// Functions
// Creating a new node
void list::create()
{
struct node *nxt_node,*pre_node;
int value,no,i;
start=nxt_node=pre_node=NULL;
cout<<" How many nodes :: ";
cin>>no;
cout<<" Enter "<<no<<" Elements :: ";
for(i=1;i<=no;i++)
{
cout<<" Enter [ "<<i<<" ] Element :: ";
cin>>value;
nxt_node=new node;
nxt_node->data=value;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
}
cout<<" The list is created! ";
}
// Displaying LIST
void list::show()
{
struct node *ptr=start;
cout<<" The List is :: ";
while(ptr!=NULL)
{
cout<<ptr->data<<" -> ";
ptr=ptr->next;
}
cout<<" ";
}
void list::merge(list l1,list l2)
{
struct node *nxt_node,*pre_node,*pptr,*qptr;
int dat;
pptr=l1.start;
qptr=l2.start;
start=nxt_node=pre_node=NULL;
while(pptr!=NULL && qptr!=NULL)
{
if(pptr->data<=qptr->data)
{
dat=pptr->data;
pptr=pptr->next;
}
else
{
dat=qptr->data;
qptr=qptr->next;
}
nxt_node=new node;
nxt_node->data=dat;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
}
if(pptr==NULL)
{
while(qptr!=NULL)
{
nxt_node=new node;
nxt_node->data=qptr->data;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
qptr=qptr->next;
}
}
else if(qptr==NULL)
{
while(pptr!=NULL)
{
nxt_node=new node;
nxt_node->data=pptr->data;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
pptr=pptr->next;
}
}
cout<<" The lists are merged....... ";
return;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.