7-1 两个有序链表序列的合并 分数 40 作者 DS课程组 单位 浙江大学 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

已知两个非降序链表序列S1和S2，我们需要设计一个函数来构造出S1和S2的合并后的新链表S3。输入的序列分为两行，每行用空格分隔数字，-1表示序列的结尾。输出要求是以非降序排列的链表。如果新链表为空，则输出NULL。

为了解决这个问题，我们可以采用以下步骤：

1. 首先，我们需要读取输入，获取两个非降序链表序列S1和S2。

2. 然后，我们可以创建一个新的链表S3，并初始化为空。

3. 接下来，我们可以使用两个指针分别指向S1和S2的头节点。

4. 然后，我们可以比较指针所指的节点的值，将较小的节点加入到S3中，并将对应的指针向后移动一位。

5. 重复上述步骤，直到其中一个链表遍历完毕。

6. 最后，我们需要将剩余的节点加入到S3中。

7. 最后，我们可以返回合并后的链表S3。

通过以上步骤，我们可以实现合并两个有序链表的操作。在输出时，我们需要将新链表S3的节点值按照非降序排列输出，数字之间用空格分隔，结尾不能有多余的空格。如果新链表S3为空，则输出NULL。

相关问题

两个有序链表序列的交集 分数 20 作者 DS课程组 单位 浙江大学 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

可以使用双指针来解决这个问题。我们用两个指针 p1 和 p2 分别指向 S1 和 S2 的头节点，然后比较这两个节点的值。

如果 p1 所指的节点的值小于 p2 所指的节点的值，那么 p1 向后移动一位；如果 p2 所指的节点的值小于 p1 所指的节点的值，那么 p2 向后移动一位；如果 p1 和 p2 所指的节点的值相等，那么将这个节点加入到 S3 中，并同时将 p1 和 p2 向后移动一位。

重复上述过程直到 p1 或 p2 到达链表的末尾，此时 S3 中存储的就是 S1 和 S2 的交集。

下面是具体实现的代码：

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

这是一道数据结构中比较经典的链表问题，可以采用双指针法来解决。

具体做法是，维护两个指针p1和p2，分别指向S1和S2的头结点。比较p1和p2所指节点的值，将较小的节点加入到新的链表S3中，并将指向该节点的指针向后移动一位。重复该过程，直到p1和p2中有一个到达了链表尾部。若此时还有节点未加入新链表S3中，则直接将其加入到S3的尾部。

下面是C++代码实现：