题解 | #合并两个排序的链表#

O(N)空间：

typedef struct ListNode Node;

Node* Merge(Node* Head1, Node* Head2)
{
	Node* p1, * p2;
	Node* Head = (Node*)malloc(sizeof(Node));
	Node* HeadH = Head;
	Node* tmp;
	Head->next = NULL;
	if (!Head1)
		return Head2;
	if (!Head2)
		return Head1;
	p1 = Head1;
	p2 = Head2;
	if (p1->val > p2->val)
	{
		Head->val = p2->val;
		p2 = p2->next;
	}
		
	else
	{
		Head->val = p1->val;
		p1 = p1->next;
	}
		
	while (p1 && p2)
	{
		tmp = (Node*)malloc(sizeof(Node));
		Head->next = tmp;
		Head = tmp;
		Head->next = NULL;
		if (p1->val > p2->val)
		{
			Head->val = p2->val;
			p2 = p2->next;
		}

		else
		{
			Head->val = p1->val;
			p1 = p1->next;
		}
	}
	if (p1)
		Head->next = p1;
	if (p2)
		Head->next = p2;

	return HeadH;
}

O(1)空间：

typedef struct ListNode Node;

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {

	Node* tmp;
	if (!pHead1)
		return pHead2;
	if (!pHead2)
		return pHead1;
    
		if (pHead1->val < pHead2->val)
		{
			tmp = pHead1;
            tmp->next = Merge(pHead1->next,pHead2);
		}
		else
		{
            tmp = pHead2;
			tmp->next = Merge(pHead1,pHead2->next);
		}
	return tmp;
}