合并两个有序链表，合并之后依旧有序

解法一   使用递归

struct list_node
{
	int data;
	list_node* next;

	list_node(int data)
		:data(data)
		, next(NULL)
	{}
};

//  1  递归法   

list_node* R_mergc(list_node* l1, list_node* l2)
{
	if (l1 == NULL)
	{
		return l2;
	}
	else if (l2 == NULL)
	{
		return l1;
	}


	//下边的要注意返回值
	//方法一
	/*if (l1->data < l2->data)
	{
		l1->next = R_mergc(l1->next, l2);
		return l1;
	}
	else
	{
		l2->next = R_mergc(l2->next, l1);
		return l2;
	}*/

	//方法二
	list_node* tmp = NULL;
	if (l1->data < l2->data)
	{
		tmp = l1;
		tmp->next = R_mergc(tmp->next, l2);
	}
	else
	{
		tmp = l2;
		tmp->next = R_mergc(tmp->next, l1);
	}
	return tmp;
}

解法二  

struct list_node
{
	int data;
	list_node* next;

	list_node(int data)
		:data(data)
		, next(NULL)
	{}
};

//  2 非递归

list_node* mergc(list_node* l1, list_node* l2)
{
	if (NULL == l1)
	{
		return l2;
	}
	else if (NULL == l2)
	{
		return l1;
	}
	list_node* head = NULL;  //用作返回的头结点
	list_node* p1 = l1;  //用作 l1 的零时变量
	list_node* p2 = l2;	 //用作 l2 的零时变量

	if (p1->data < p2->data)
	{
		head = p1;
		p1 = p1->next;
	}
	else
	{
		head = p2;
		p2 = p2->next;
	}

	list_node* cur = head;  //

	while (p1 && p2)
	{
		if (p1->data < p2->data)
		{
			cur->next = p1;
			cur = cur->next;
			p1 = p1->next;
		}
		else
		{
			cur->next = p2;
			cur = cur->next;
			p2 = p2->next;
		}
	}

	if (p1 != NULL)
	{
		cur->next = p1;
	}
	else
	{
		cur->next = p2;
	}
	return head;
}