Leetcode32 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

我的思路，这个题目要是不是可以用最简单的方式解决呢？假设两个链表的长度相等。那么遍历链表l1,然后依次让l2插入到l1后面。 但是之后发现，题目中有可能是长度不一样的，那么我就更改为如果l2比l1长，那么就从l1插入到l2，反之亦然。但是例子中又有l1或l2为空的情况，我又设置为l1为空就返回l2,反之亦然。 但是我在这里卡住了。

输入 [5] [1,2,4] 输出 [1,5,2,4] 预期结果 [1,2,4,5]

这里明显l2比l1长，那么应该讲l1插入到l2中，最终结果应该是1,5,2,4，后面认真审题后发现，题目为讲两个有序链表合并为一个新的有序链表并返回。也就是说，

1. 输入的两个链表都是有序的，而且输入的链表可能为0；
2. 输出的链表也是有序的，而且是通过输入链表组合而得到的。 重新整理一下思路，首先对边界进行限制，即考虑l1和l2为null的情况，然后将l1中的元素插入到l2中去。

写了一段时间，不会，直接看答案吧， 有2中解法，我使用了迭代的方法，成功了，唯一需要注意的是最后一个元素需要单独添加。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
	if (l1==NULL)
	{
		return l2;
	}
	if (l2 == NULL)
	{
		return l1;
	}
	ListNode* p1 = l1;
	ListNode* p2 = l2;
	ListNode* head = new ListNode(0);
	ListNode* p = head;
	//迭代方法
	while ( p2!=NULL && p1!=NULL)
	{
		if (p1->val < p2->val)
		{
			p->next = p1;
			p1 = p1->next;
		}
		else
		{
			p->next = p2;
			p2 = p2->next;
		}
		p = p->next;
	}
	if (p1 == NULL)
	{
		p->next = p2;
	}
	if (p2 == NULL)
	{
		p->next = p1;
	}
	return head->next;
}