#include
using namespace std;
class node
{
public:
int data;
node *next;
node(int d)
{
data = d;
next = NULL;
}
};
void insertathead(node *&head, int d)
{
// the problem here is that we r passing it by value and the change will not get reflected inside the main function
// solution is we have to pass the head pointer by reference
if (head == NULL)
{
head = new node(d);
return;
}
// why dynamic allocation—>node will get destroyed after static allocation…so dynamic allocation will help us to keep the track of all lists without getting destroyed
node *n = new node(d);
n->next = head;
head = n;
}
node *input()
{
int d;
cin >> d;
node *head = NULL;
while (d>0)
{
insertathead(head, d);
d–;
}
return head;
}
int calculate_the_length(node *head)
{
node *temp = head;
int cnt = 0;
while (temp != NULL)
{
cnt++;
temp = temp->next;
}
return cnt;
}
node *kthfromend(node *head, int k)
{
if (head == NULL or head->next == NULL)
{
return head;
}
node *slow = head;
node *fast = head;
while (k > 0)
{
fast = fast->next;
k--;
}
while (fast != NULL and fast->next != NULL)
{
slow = slow->next;
fast = fast->next;
}
slow = slow->next;
return slow;
}
void print(node *head)
{
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
}
ostream& operator<<(ostream &os, node *head)
{
print(head);
return os;
}
istream &operator>>(istream &cin, node *&head)
{
head = input();
return cin;
}
node *merge(node *a, node *b)
{
if (a == NULL)
{
return b;
}
if (b == NULL)
{
return a;
}
// take a head pointer
node *c;
if (a->data < b->data)
{
c = a;
c->next = merge(a->next, b);
}
else
{
c = b;
c->next = merge(a, b->next);
}
return c;
}
int main()
{
int t;
cin>>t;
while(t–){
nodehead1 = NULL;
nodehead2 = NULL;
int n1;
cin>>n1;
for(int i=1;i<=n1;i++){
int d;
cin>>d;
insertathead(head1,d);
}
int n2;
cin>>n2;
for(int i=1;i<=n2;i++){
int d;
cin>>d;
insertathead(head2,d);
}
node*n = merge(head1,head2);
cout<<n<<endl;
}
return 0;
}