[数据结构与算法]21. 合并两个有序链表（来源:力扣（LeetCode））

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
?

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

解题思路：

1.先判断是否有空链表，若有空链表，则直接返回另一个链表。

    if(!list1){
        return list2;
    }
    if(!list2){
        return list1;
    }

2.为答案链表开辟空间。

struct ListNode *L = (struct ListNode *)malloc(sizeof(struct ListNode));

3.在两个链表都不为空时，判断两个链表的值，将较小值存入新链表中。

while(p1 && p2){
        if(p1->val <= p2->val){
            s->next = p1;
            s = p1;
            p1 = p1->next;
        }
        else{
          s->next = p2;
          s = p2; 
          p2 = p2->next;
        }
    }

4.当一个链表遍历完之后，将另一个链表剩下的值直接存入新链表中。

    if(!p1){
        s->next = p2; 
    }
    if(!p2){
        s->next = p1;
    } 

完整代码如下：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

    if(!list1){
        return list2;
    }
    if(!list2){
        return list1;
    }
    struct ListNode *L = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *p1 = list1, *p2 = list2;
    struct ListNode *s = L;
    while(p1 && p2){
        if(p1->val <= p2->val){
            s->next = p1;
            s = p1;
            p1 = p1->next;
        }
        else{
          s->next = p2;
          s = p2; 
          p2 = p2->next;
        }
    }
    if(!p1){
        s->next = p2; 
    }
    if(!p2){
        s->next = p1;
    } 
    return L->next;
}