给定两个升序数组，合并两个数组为一个升序数组

struct LinkedNode
{
	int val;
	LinkedNode* next;
	LinkedNode() : val(0), next(nullptr) {}
	LinkedNode(int x) : val(x), next(nullptr) {}
	LinkedNode(int x, LinkedNode* ptr) : val(x), next(ptr) {}
};

class Solution_Recursion
{
public:
	LinkedNode* mergeTwo(LinkedNode* list1, LinkedNode* list2)
	{
		if (list1 == nullptr) return list2;
		else if (list2 == nullptr) return list1;
		else if (list1->val < list2->val)
		{
			list1->next = mergeTwo(list1->next, list2);
			return list1;
		}
		else
		{
			list2->next = mergeTwo(list1, list2->next);
			return list2;
		}
	}
};

class Solution_Iteration
{
public:
	LinkedNode* mergeTwo(LinkedNode* list1, LinkedNode* list2)
	{
		LinkedNode* templist = new LinkedNode();
		LinkedNode* head = templist;
		while (list1 && list2)
		{
			if (list1->val < list2->val)
			{
				templist->next = list1;
				list1 = list1->next;
			}
			else
			{
				templist->next = list2;
				list2 = list2->next;
			}
			templist = templist->next;
		}
		templist->next = list1 == nullptr ? list2 : list1;
		delete templist;
		return head->next;
	}
};