7-1 两个有序链表序列的合并 分数 40 作者 DS课程组 单位 浙江大学 已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并后的新的非降序链表S3。
时间: 2024-03-16 17:33:35 浏览: 96
已知两个非降序链表序列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。
相关问题
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 # 返回合并后的链表的头节点
```
两个有序链表序列的交集 分数 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 的交集。
下面是具体实现的代码: