归并

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
	ListNode *pNewHead = nullptr;
	ListNode *pCurrent = nullptr;

	while (pHead1 && pHead2)
	{
		if (pHead1->val > pHead2->val)
		{
			if (pNewHead)
			{
				pCurrent->next = pHead1;
				pHead1 = pHead1->next;
				pCurrent = pCurrent->next;
				pCurrent->next = nullptr;
			}
			else
			{
				pNewHead = pHead1;
				pHead1 = pHead1->next;
				pNewHead->next = nullptr;
				pCurrent = pNewHead;
			}
		}
		else
		{
			if (pNewHead)
			{
				pCurrent->next = pHead2;
				pHead2 = pHead2->next;
				pCurrent = pCurrent->next;
				pCurrent->next = nullptr;
			}
			else
			{
				pNewHead = pHead2;
				pHead2 = pHead2->next;
				pNewHead->next = nullptr;
				pCurrent = pNewHead;
			}
		}
	}

	while (pHead1)
	{
		if (pNewHead)
		{
			pCurrent->next = pHead1;
			pHead1 = pHead1->next;
			pCurrent = pCurrent->next;
			pCurrent->next = nullptr;
		}
		else
		{
			pNewHead = pHead1;
			pHead1 = pHead1->next;
			pNewHead->next = nullptr;
			pCurrent = pNewHead;
		}
	}

	while (pHead2)
	{
		if (pNewHead)
		{
			pCurrent->next = pHead2;
			pHead2 = pHead2->next;
			pCurrent = pCurrent->next;
			pCurrent->next = nullptr;
		}
		else
		{
			pNewHead = pHead2;
			pHead2 = pHead2->next;
			pNewHead->next = nullptr;
			pCurrent = pNewHead;
		}
	}

	return pNewHead;
}