7-1 两个有序链表序列的合并 分数 20 作者 DS课程组 单位 浙江大学 已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并后的新的非降序链表S3。 输入格式: 输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。 输出格式: 在一行中输出合并后新的非降序链表,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。
时间: 2024-03-16 07:02:56 浏览: 33
这是一道数据结构中比较经典的链表问题,可以采用双指针法来解决。
具体做法是,维护两个指针p1和p2,分别指向S1和S2的头结点。比较p1和p2所指节点的值,将较小的节点加入到新的链表S3中,并将指向该节点的指针向后移动一位。重复该过程,直到p1和p2中有一个到达了链表尾部。若此时还有节点未加入新链表S3中,则直接将其加入到S3的尾部。
下面是C++代码实现:
相关问题
7-1 两个有序链表序列的合并 分数 50 作者 DS课程组 单位 浙江大学
两个有序链表序列的合并是指将两个有序链表按照元素大小的顺序合并成一个新的有序链表。具体的合并过程如下:
1. 创建一个新的链表,用于存储合并后的结果。
2. 初始化两个指针,分别指向两个有序链表的头节点。
3. 比较两个指针所指节点的值,将较小的节点添加到新链表中,并将对应链表的指针后移一位。
4. 重复步骤3,直到其中一个链表遍历完毕。
5. 将剩余未遍历完的链表直接连接到新链表的末尾。
6. 返回新链表作为合并后的结果。
以下是一个示例代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0) # 创建一个虚拟头节点
curr = dummy # 当前节点指针
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
# 将剩余未遍历完的链表直接连接到新链表的末尾
if l1:
curr.next = l1
if l2:
curr.next = l2
return dummy.next # 返回合并后的链表的头节点
```
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。