struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//依次从头开始比较链表1和链表2的元素，小的头插到新链表中去
//定义一个尾节点，方便尾插
if(list1 == NULL)
return list2;
if(list2 == NULL)
return list1;
struct ListNode* newhead = NULL;
struct ListNode* tail = NULL;
while(list1 && list2)
{
if(list1->val <= list2->val)
{
if(tail == NULL)//如果初始是NULL，那么直接赋值；
{
newhead = list1;
tail = list1;
}
else
{
tail->next = list1;
tail = tail->next;
}
list1 = list1->next;
}
else
{
if(tail == NULL)
{
newhead = list2;
tail = list2;
}
else
{
tail->next = list2;
tail = tail->next;
}
list2 = list2->next;
}
}
if(list1)//这里看看哪个链表还没有比较结束，就直接尾插到新链表的后面
tail->next = list1;
if(list2)
tail->next = list2;
return newhead;
}
