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

以下是C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node *PtrToNode;
struct Node {
    int Data;
    PtrToNode Next;
};

typedef PtrToNode List;

List ReadList(); // 读取链表
List Merge(List L1, List L2); // 合并链表
void PrintList(List L); // 输出链表

int main()
{
    List L1, L2, L3;
    L1 = ReadList();
    L2 = ReadList();
    L3 = Merge(L1, L2);
    PrintList(L3);
    return 0;
}

List ReadList()
{
    int n;
    scanf("%d", &n);
    List L = (List)malloc(sizeof(struct Node)); // 头结点
    L->Next = NULL;
    PtrToNode rear = L; // rear指向链表最后一个结点
    while (n != -1) {
        PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node));
        newNode->Data = n;
        newNode->Next = NULL;
        rear->Next = newNode;
        rear = newNode;
        scanf("%d", &n);
    }
    return L;
}

List Merge(List L1, List L2)
{
    List L3 = (List)malloc(sizeof(struct Node)); // 头结点
    L3->Next = NULL;
    PtrToNode rear = L3; // rear指向链表最后一个结点
    PtrToNode p1 = L1->Next, p2 = L2->Next;
    while (p1 && p2) {
        if (p1->Data < p2->Data) {
            rear->Next = p1;
            p1 = p1->Next;
            rear = rear->Next;
        } else {
            rear->Next = p2;
            p2 = p2->Next;
            rear = rear->Next;
        }
    }
    // 将未加入链表的节点加入到L3中
    if (p1) {
        rear->Next = p1;
    } else {
        rear->Next = p2;
    }
    // 释放L1和L2的头结点
    free(L1);
    free(L2);
    return L3;
}

void PrintList(List L)
{
    if (L->Next == NULL) {
        printf("NULL");
    } else {
        PtrToNode p = L->Next;
        while (p) {
            printf("%d ", p->Data);
            p = p->Next;
        }
    }
}

在主函数中，先调用`ReadList()`读取输入的两个链表，然后调用`Merge()`合并两个链表，最后调用`PrintList()`输出合并后的链表即可。

在`ReadList()`函数中，首先读入第一个数字n，然后创建一个头结点和一个指向头结点的指针L，rear指向链表最后一个结点。接着循环读入数字，创建一个新节点，将其加入到链表尾部，并将rear指向新节点。当读入-1时，停止循环，返回头结点L。

在`Merge()`函数中，首先创建一个头结点和一个指向头结点的指针L3，rear指向链表最后一个结点。再定义两个指针p1和p2，分别指向L1和L2的第一个节点。循环比较p1和p2所指节点的值，将较小的节点加入到L3中，并将指向该节点的指针向后移动一位。重复该过程，直到p1和p2中有一个到达了链表尾部。若此时还有节点未加入L3中，则直接将其加入到L3的尾部。最后释放L1和L2的头结点，并返回L3。

在`PrintList()`函数中，如果链表为空，则输出NULL，否则循环遍历链表中的每个节点，输出节点的值。