目录
1、题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
2、思路
可以创建一个哨兵节点作为辅助节点，它是合并后的新链表的头节点的前一个节点。使用哨兵节点可以避免处理空链表或只有一个元素的特殊情况。
之后比较list1和list2节点值的大小，若list1节点的值小于list2节点的值，则把list1节点加入到新链表表尾，并让list1指向下一个节点；若list2节点的值小于list1节点的值，则把list2节点加入到新链表表尾，并让list2指向下一个节点；若list1节点的值等于list2节点的值，无论把哪个链表的节点加入到新链表都是一样的。一直循环下去，直到有一个链表为空。
循环结束之后，若一个链表还有剩余节点，则把它加入到新链表的末尾。最后，返回新链表的第一个节点，也就是哨兵节点的下一个节点。
3、代码
//合并两个有序链表
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode sentry={};//定义了一个哨兵节点sentry，并初始化其所有成员为0;sentry作为一个临时的头节点，它的next指针将指向合并后的链表的第一个元素
struct ListNode* pointer=&sentry;//pointer指针初始化为指向哨兵节点，之后始终指向新链表的最后一个节点
while(list1&&list2){//循环遍历两个链表，直到其中一个链表遍历完
if(list1->val<list2->val){//若list1节点的值小于list2节点的值，则把list1节点加入到新链表表尾，并让list1指向下一个节点
pointer->next=list1;
list1=list1->next;
}else{//若list2节点的值小于等于list1节点的值，则把list2节点加入到新链表表尾，并让list2指向下一个节点
pointer->next=list2;
list2=list2->next;
}
pointer=pointer->next;//pointer指针也移动到新链表的下一个位置
}
pointer->next=list1?list1:list2;//将剩余的链表（未遍历完的部分）直接加到新链表的末尾
return sentry.next;//返回哨兵节点的next指针，它指向合并后的新链表的第一个元素
//哨兵节点是一个辅助节点，它本身并不属于合并后的新链表
}