已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3

算法思路：

可以使用归并排序的思想，将S1和S2中的元素逐个比较，将较小的元素加入S3中，直到S1或S2中的元素遍历完毕。最后，将S1或S2中剩余的元素加入S3中即可。

算法步骤：

1.设置两个指针p1和p2分别指向S1和S2的头结点；

2.比较p1和p2指向的结点的值的大小，将较小的结点加入S3中，并将p1或p2指向下一个结点；

3.如果S1或S2中还有剩余的结点，将其加入S3中。

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* p1 = l1; //指向链表l1的指针
    struct ListNode* p2 = l2; //指向链表l2的指针
    struct ListNode* p = NULL; //指向新链表的指针
    struct ListNode* head = NULL; //新链表的头结点
    //判断l1和l2是否为空链表
    if(l1 == NULL) {
        return l2;
    }
    if(l2 == NULL) {
        return l1;
    }
    //确定新链表的头结点
    if(p1->val <= p2->val) {
        head = p1;
        p1 = p1->next;
    } else {
        head = p2;
        p2 = p2->next;
    }
    p = head;
    //将l1和l2中的较小值加入新链表中
    while(p1 && p2) {
        if(p1->val <= p2->val) {
            p->next = p1;
            p1 = p1->next;
        } else {
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next;
    }
    //将l1或l2中剩余的结点加入新链表中
    if(p1) {
        p->next = p1;
    }
    if(p2) {
        p->next = p2;
    }
    return head;
}