7-4 两个有序链表序列的合并 (20 分)

### 回答1：
题目描述

将两个非降序列合并为一个非降序列。

输入格式

输入样例

链表 1： 1→3→5→7→9
链表 2： 2→4→6→8→10

输出样例

链表： 1→2→3→4→5→6→7→8→9→10

算法1

(指针) $O(n)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

### 回答2：
有序链表是指链表中的元素按照某种规则有序排列的链表，如果要将两个有序链表合并成一个有序链表，可以使用归并排序的思想。首先要进行链表的遍历，以找到两个链表中的最小结点，然后将其合并为一个新链表的第一个结点，接着继续遍历两个链表，每当找到两个链表中的最小结点，就将其加入新链表中。

具体的操作过程如下所示：

1. 定义一个指针pNew来表示新链表的头结点，pNew初始值为null。

2. 定义指针pCurr1来遍历链表1，指针pCurr2来遍历链表2。

3. 判断pCurr1和pCurr2是否都为null，如果是，则链表遍历结束。

4. 判断pCurr1和pCurr2是否存在null，如果有，则将另外一个链表中未处理的结点，直接加入新链表中。

5. 判断pCurr1和pCurr2值的大小，如果pCurr1小于等于pCurr2的值，则将pCurr1加入新链表中，pCurr1指向下一个结点；否则将pCurr2加入新链表中，pCurr2指向下一个结点。

6. 将pNew指针指向新链表的第一个结点。

7. 返回pNew指针。

需要注意的是，在合并两个有序链表的过程中，需要修改指针指向，避免链表节点丢失。在使用链表合并的算法时，需要注意代码的可读性和可维护性，并遵循代码的规范化编写，才能将工作效率最大化，并使程序更加易于维护。同时，还需要注意链表结点的动态内存分配和释放，避免程序运行中出现内存泄漏或者内存溢出的问题。

### 回答3：
7-4 两个有序链表序列的合并是一道常见的链表操作题目。题目给定两个有序的链表序列，要求将它们合并成一个有序的链表序列。

解题思路：

1. 定义一个虚拟头结点 dummy，用来辅助我们构建新的链表。

2. 定义两个指针 p 和 q 分别指向两个链表的头结点。

3. 遍历两个链表，比较 p 和 q 指向的结点的大小，将较小的结点添加到新链表的尾部，并将对应指针向后移动。

4. 如果其中一个链表已经遍历完了，将另一个没有遍历完的链表的剩余部分直接添加到新链表尾部即可。

5. 返回虚拟头结点的下一个结点即为合并后的链表。

代码实现：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // 定义虚拟头结点
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = NULL;
    // 定义辅助指针和新链表的尾结点
    struct ListNode* p = l1;
    struct ListNode* q = l2;
    struct ListNode* tail = dummy;
    // 遍历两个链表，构建新链表
    while (p != NULL && q != NULL) {
        if (p->val <= q->val) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
    }
    // 处理未遍历完的链表
    if (p != NULL) {
        tail->next = p;
    } else if (q != NULL) {
        tail->next = q;
    }
    // 返回新链表的头结点
    struct ListNode* head = dummy->next;
    free(dummy);
    return head;
}

时间复杂度为 $O(m+n)$，其中 $m$ 和 $n$ 分别为两个链表的长度。空间复杂度为 $O(1)$，只需要常数级的额外空间来存储一些指针变量。