链表面试题之合并两个有序单链表
题目描述：
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
解析：
首先先取得小的结点作为头结点；
然后拿到L1, L2中较小的结点进行尾插，直到其中一个链表遍历完并且插入完结束。
最后将未遍历完的链表 连接 到tail指针后即可。
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
if (l1 == NULL)
return l2;
else if (l2 == NULL)
return l1;
// 先取小的结点作为头
struct ListNode* head, *tail;
if (l1->val < l2->val)
{
head = l1;
l1 = l1->next;
}
else
{
head = l2;
l2 = l2->next;
}
// 拿小的结点进行尾插
tail = head;
while (l1 && l2) //其中有一个链表结束
{
if (l1->val < l2->val)
{
tail->next = l1;
l1 = l1->next;
}
else
{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if (l1 != NULL)
tail->next = l1;
if (l2 != NULL)
tail->next = l2;
return head;
}
