两个有序链表序列的合并 c++

思路：

1. 定义一个新的链表作为合并后的链表，初始化为 NULL。
2. 分别遍历两个有序链表，比较当前节点的大小，将较小的节点插入到新链表的末尾。
3. 如果有一个链表遍历完了，则将另一个链表的剩余节点直接插入到新链表的末尾。
4. 返回合并后的链表。

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head = NULL;  // 定义新链表的头节点
    struct ListNode* tail = NULL;  // 定义新链表的尾节点
    // 分别遍历两个链表
    while (l1 != NULL && l2 != NULL) {
        struct ListNode* node = NULL;  // 定义需要插入的节点
        if (l1->val < l2->val) {
            node = l1;
            l1 = l1->next;
        } else {
            node = l2;
            l2 = l2->next;
        }
        // 将节点插入到新链表的末尾
        if (tail == NULL) {  // 新链表为空，node为头节点
            head = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    // 将剩余节点插入到新链表的末尾
    if (l1 != NULL) {
        if (tail == NULL) {  // 新链表为空，l1为头节点
            head = l1;
        } else {
            tail->next = l1;
        }
    } else if (l2 != NULL) {
        if (tail == NULL) {  // 新链表为空，l2为头节点
            head = l2;
        } else {
            tail->next = l2;
        }
    }
    return head;
}