已知两个非降序链表序列s1与s2，设计函数构造出s1与s2合并后的新的非降序链表s3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。 输出格式: 在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出null。

### 回答1：
算法思路：

1. 定义两个指针p1和p2，分别指向s1和s2的头结点；

2. 定义一个新的链表s3，以及一个指针p3，初始时p3指向s3的头结点；

3. 比较p1和p2所指向的节点的值，将较小的节点插入到s3中，并将p3指向新插入的节点；

4. 重复步骤3，直到p1或p2为空；

5. 将p1或p2剩余的节点插入到s3中；

6. 返回s3。

Python代码实现：

class ListNode:
    def __init__(self, val=, next=None):
        self.val = val
        self.next = next

def merge(s1: ListNode, s2: ListNode) -> ListNode:
    p1, p2 = s1, s2
    s3 = ListNode()
    p3 = s3

    while p1 and p2:
        if p1.val <= p2.val:
            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

    return s3.next

# 读入两个链表
s1 = ListNode()
p1 = s1
for x in input().split():
    if x == '-1':
        break
    p1.next = ListNode(int(x))
    p1 = p1.next

s2 = ListNode()
p2 = s2
for x in input().split():
    if x == '-1':
        break
    p2.next = ListNode(int(x))
    p2 = p2.next

# 合并两个链表
s3 = merge(s1.next, s2.next)

# 输出合并后的链表
if s3:
    res = []
    while s3:
        res.append(str(s3.val))
        s3 = s3.next
    print(' '.join(res))
else:
    print('null')

C++代码实现：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* merge(ListNode* s1, ListNode* s2) {
    ListNode* p1 = s1;
    ListNode* p2 = s2;
    ListNode* s3 = new ListNode();
    ListNode* p3 = s3;

    while (p1 && p2) {
        if (p1->val <= p2->val) {
            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;
    }

    return s3->next;
}

int main() {
    ListNode* s1 = new ListNode();
    ListNode* p1 = s1;
    int x;
    while (cin >> x && x != -1) {
        p1->next = new ListNode(x);
        p1 = p1->next;
    }

    ListNode* s2 = new ListNode();
    ListNode* p2 = s2;
    while (cin >> x && x != -1) {
        p2->next = new ListNode(x);
        p2 = p2->next;
    }

    ListNode* s3 = merge(s1->next, s2->next);

    if (s3) {
        while (s3) {
            cout << s3->val << " ";
            s3 = s3->next;
        }
    } else {
        cout << "null";
    }

    return ;
}

### 回答2：
题目描述

已知两个非降序链表序列s1与s2，设计函数构造出s1与s2合并后的新的非降序链表s3。

输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用-1表示序列的结尾（-1不属于这个序列）。数字用空格间隔。

输出格式:
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

样例输入
1 3 5 -1
2 4 6 8 10 -1
样例输出
1 2 3 4 5 6 8 10

算法1

C++ 代码

### 回答3：
解题思路：

- 首先，我们需要先读入两个非降序链表序列s1与s2。
- 然后，我们需要新建一个非降序链表s3来存储s1与s2合并后的结果。
- 由于s1与s2都是非降序序列，所以我们可以每次比较s1与s2的首元素，将较小的元素添加到s3中，并将相应的指针后移，直到s1或s2为空。
- 如果s1与s2有一个已经为空，我们只需要将另一个非空的链表剩余的元素全部添加到s3的末尾即可。
- 最后，我们输出s3中的元素即可。

代码实现：

# 定义链表节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

# 定义合并链表的函数
def mergeLists(s1, s2):
# 初始化s3为空链表
s3 = ListNode()
p = s3 # 定义指针p指向s3的末尾

# 当s1与s2都不为空时，比较首元素大小，将较小的元素添加到s3中
while s1 and s2:
if s1.val <= s2.val:
p.next = ListNode(s1.val)
s1 = s1.next
else:
p.next = ListNode(s2.val)
s2 = s2.next
p = p.next

# 当s1或s2有一个为空时，将另一个非空链表剩余的元素添加到s3的末尾
if s1:
p.next = s1
if s2:
p.next = s2

return s3.next # 返回新的合并后的链表

# 读入两个非降序链表序列s1与s2
s1 = list(map(int, input().split()))
s1.pop() # 去掉结尾的-1
s2 = list(map(int, input().split()))
s2.pop() # 去掉结尾的-1

# 将s1与s2转换成链表形式
s1_head = ListNode()
p = s1_head
for num in s1:
p.next = ListNode(num)
p = p.next
s1 = s1_head.next

s2_head = ListNode()
p = s2_head
for num in s2:
p.next = ListNode(num)
p = p.next
s2 = s2_head.next

# 合并s1与s2，得到新的非降序链表s3
s3 = mergeLists(s1, s2)

# 输出s3中的元素
if s3:
res = []
while s3:
res.append(str(s3.val))
s3 = s3.next
print(' '.join(res))
else:
print('null') # 如果s3为空，输出null