Write this function given the template below for linked lists in C++ with the gi

Question

Write this function given the template below for linked lists in C++ with the given requirements:

Given implementation of Linked list that can be helpful for writing function:

QUESTION: Function: concatsort assumes both list a and b are in SOrted (non-descending) order and merges them into a single sorted list with the same * elements This single sorted list is stored in a while b becomes empty. if either of given lists are not sorted, implementation dependent - i.e., don't worry * we blame the caller and the behavior is about it! Condition in which both parameters are the same list (not merely "equal"), the function simply does nothing and returns. This can be tested with simple pointer comparison Example: a: [2 3 4 9 10 30] b: [5 8811 20 40] after call a.merge with (b): a: [2 3 45 889 10 11 20 30 40] REQUIREMENTS : Runtime Must be linear in the length of the resulting merged list (or using variables above, O (a.length () +b.length should not allocate ANY new list nodes - it should just re-link existing x nodes. Cannot change function parameters void merge_with (List &other)

Explanation / Answer

#include<iostream>

class list

{

struct Node

{

int data;

struct Node *next;  

};

struct node *start;

public:

void create_list();

void show_list();

void merge_list(list,list);  

};

int main()

{

  

list list1,list2,list3;

cout<<"Enter the First List ";

list1.create(); // create a first list

cout<<"Enter the Second List ";

list2.create(); // create a second list

cout<<"The first list is";

list1.show();

cout<<"The second list is";

list2.show();

list.merge(l1,l2);

cout<<"The merged list is";

list3.show();

return 0;

}

// Creating a new Node

void list::create_list()

{

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++)

{

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<<"list is created!";

}

void list::show_list()

{

struct Node *ptr=start;

cout<<"The List is ";

while(ptr!=NULL)

{

cout<<ptr->data<<" -> ";

ptr=ptr->next;

}  

}

void list::merge_list(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;

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.