题目:
题解:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//如果List1和list2中有一个为空就直接返回另一个链表
if(list1 == NULL)
{
return list2;
}
if(list2 == NULL)
{
return list1;
}
//定义l1,l2指针分别指向list1和list2的头节点
ListNode* l1, *l2;
ListNode* newhead, *newtail;
//给新链表的开辟一个哨兵位
newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
l1 = list1,l2 = list2;
while(l1 && l2)
{
if(l1->val <= l2->val)
{
newtail->next = l1;
newtail = newtail->next;
l1 = l1->next;
}
else
{
newtail->next = l2;
newtail = newtail->next;
l2 = l2->next;
}
}
if(l1)
{
newtail->next = l1;
}
if(l2)
{
newtail->next = l2;
}
//新链表的第一个节点是头节点为无效数据,因此返回头节点的next
return newhead->next;
}