合并升序链表，简单易懂

注意题中给出的l1和l2都是不带头结点的链表，所以最后返回的新链表指针也是直接从第一个结点开始的，但我习惯了用带头结点的，最后往后移一位就行

#include<bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) { //l1、l2指向两个链表的首元结点
        ListNode* p = l1, * q = l2;
        ListNode* l3 = (ListNode*)malloc(sizeof(ListNode)); //创建头结点
        ListNode* s = l3;
        while (p != NULL && q != NULL) //l1和l2都不为空时进行比较，把小的接在l3后面
        {
            s->next = (ListNode*)malloc(sizeof(ListNode));
            s = s->next;
            if (p->val < q->val)
            {
                s->val = p->val;
                p = p->next;
            }
            else
            {
                s->val = q->val;
                q = q->next;
            }
        }
        //若l1或l2还有不为空的，则将其所有结点全部接在l3后面即可
        while (p != NULL) 
        {
            s->next = (ListNode*)malloc(sizeof(ListNode));
            s = s->next;
            s->val = p->val;
            p = p->next;
        }
        while (q != NULL)
        {
            s->next = (ListNode*)malloc(sizeof(ListNode));
            s = s->next;
            s->val = q->val;
            q = q->next;
        }
        s->next = NULL;
        l3 = l3->next; //l3原本指向头结点，让它后移一格指向首元结点然后返回

        return l3;
    }
};