#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct listNode {

	int* dataPtr;

	struct listNode* next;

}ListNode;



typedef struct list

{

	ListNode* head;

	ListNode* tail;

}List;

List getList();
void insertDataToEndList(List* lst, int num);
void AddNewListNodeToTail(List* lst);
ListNode* CreateListNode();
void MemoryAllocationFailed();
List merge(List lst1, List lst2);
void makeEmptyList(List* lst);
void mergeRekursion(ListNode* curr1, ListNode* curr2, List *merged);
void insertListNodeToTail(List* lst, ListNode* node);
void printList(List* lst);
void freeList(List* lst);

void main()
{

	List lst1, lst2, mergedList;

	lst1 = getList();
	lst2 = getList();

	mergedList = merge(lst1, lst2);

	printList(&mergedList);

	freeList(&mergedList);

}

List getList()
{
	List res;
	int size, num, i;

	makeEmptyList(&res);

	scanf("%d", &size);

	for (i = 0; i < size; i++)
	{
		scanf("%d", &num);
		insertDataToEndList(&res, num);
	}

	return res;

}

void insertDataToEndList(List* lst, int num)
{
	AddNewListNodeToTail(lst);
	*(lst->tail->dataPtr) = num;
}

void AddNewListNodeToTail(List* lst)
{
	ListNode* node = CreateListNode();

	if (lst->head == NULL)
	{
		lst->head = lst->tail = node;
	}
	else
	{
		lst->tail->next = node;
		lst->tail = node;
	}
}

ListNode* CreateListNode()
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (!node)
		MemoryAllocationFailed();

	node->dataPtr = (int*)malloc(sizeof(int));
	if (!(node->dataPtr))
		MemoryAllocationFailed();

	node->next = NULL;

	return node;
}

void MemoryAllocationFailed()
{
	printf("Memory Allocation Failed!");
	exit(-1);
}

List merge(List lst1, List lst2)
{
	List merged;
	makeEmptyList(&merged);
	ListNode* curr1 = lst1.head;
	ListNode* curr2 = lst2.head;

	mergeRekursion(curr1, curr2, &merged);

	return merged;

}

void makeEmptyList(List* lst)
{
	lst->head = lst->tail = NULL;
}

void mergeRekursion(ListNode* curr1, ListNode* curr2, List *merged)
{
	if (curr1 == NULL && curr2 == NULL)
		return;

	if (curr1 != NULL)
	{
		if (curr2 == NULL || *(curr1->dataPtr) > *(curr2->dataPtr))
		{
			insertListNodeToTail(merged, curr1);
			mergeRekursion(curr1->next, curr2, merged);
		}

		else
		{
			insertListNodeToTail(merged, curr2);
			mergeRekursion(curr1, curr2->next, merged);
		}
	}
	else
	{
		insertListNodeToTail(merged, curr2);
		mergeRekursion(curr1, curr2->next, merged);
	}



}

void insertListNodeToTail(List* lst, ListNode* node)
{
	if (lst->head == NULL)
	{
		lst->head = lst->tail = node;
	}
	else
	{
		lst->tail->next = node;
		lst->tail = node;
	}
}

void printList(List* lst)
{
	ListNode* curr = lst->head;
	while (curr != NULL)
	{
		printf("%d ", *(curr->dataPtr));
		curr = curr->next;
	}
	printf("\n");
}

void freeList(List* lst)
{
	ListNode* curr = lst->head, *saver;

	while (curr != NULL)
	{
		saver = curr->next;
		free(curr->dataPtr);
		free(curr);
		curr = saver;
	}
}