7-3 两个有序链表序列的合并 分数 20 作者 DS课程组 单位 浙江大学 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。 输出格式: 在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

好的，这是一道关于链表合并的问题。我可以帮您解答。

首先，我们需要先定义一个链表节点的结构体，包含两个成员：一个数值 value，一个指向下一个节点的指针 next。代码如下：

struct ListNode {
    int value;
    ListNode* next;
};

接下来，我们可以定义一个函数 merge，输入为两个链表的头指针，输出为合并后链表的头指针。具体实现如下：

ListNode* merge(ListNode* head1, ListNode* head2) {
    // 如果两个链表中有一个为空，则直接返回另一个链表的头指针
    if (!head1) return head2;
    if (!head2) return head1;

    ListNode* p1 = head1;
    ListNode* p2 = head2;
    ListNode* newHead = new ListNode;
    ListNode* p3 = newHead;

    // 遍历两个链表，将较小值的节点插入到新链表中
    while (p1 && p2) {
        if (p1->value <= p2->value) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }

    // 将未遍历完的链表接到新链表的末尾
    if (p1) p3->next = p1;
    if (p2) p3->next = p2;

    ListNode* ret = newHead->next;
    delete newHead;
    return ret;
}

在上述函数中，我们定义了三个指针：p1、p2、p3。p1 和 p2 分别指向两个链表的当前节点，p3 指向新链表的末尾。我们遍历两个链表，将较小值的节点插入到新链表中，直到其中一个链表遍历完。最后，我们将未遍历完的链表接到新链表的末尾。最后，我们将新链表的头节点的 next 指针返回，即为合并后链表的头指针。

完整代码如下：