7-2 两个有序链表序列的交集 分数 20 全屏浏览题目 切换布局 作者 ds课程组 单位
时间: 2023-11-11 07:07:19 浏览: 73
两个有序链表的交集可以通过遍历两个链表来实现。我们可以使用双指针法,分别指向两个链表的头节点,比较节点的值大小,如果相等则将该节点添加到结果链表中,并同时移动两个指针;如果不相等,则将值较小的节点所在的链表指针向后移动一位。重复这个过程,直到其中一个链表遍历完毕。
以下是一个示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersection(head1, head2):
dummy = ListNode(0)
curr = dummy
while head1 and head2:
if head1.val < head2.val:
head1 = head1.next
elif head1.val > head2.val:
head2 = head2.next
else:
curr.next = ListNode(head1.val)
curr = curr.next
head1 = head1.next
head2 = head2.next
return dummy.next
```
相关问题
7-2 两个有序链表序列的交集 分数 20 全屏浏览题目 切换布局 作者 ds课程组 单位 利用c语言写代码
可以使用C语言编写代码来找到两个有序链表的交集。下面是一个可能的实现示例:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
void insert(struct Node** headRef, int newData) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;
struct Node** current = headRef;
while (*current != NULL && (*current)->data < newNode->data) {
current = &((*current)->next);
}
newNode->next = *current;
*current = newNode;
}
struct Node* findIntersection(struct Node* list1, struct Node* list2) {
struct Node dummy;
struct Node* tail = &dummy;
dummy.next = NULL;
while (list1 != NULL && list2 != NULL) {
if (list1->data == list2->data) {
insert(&(tail->next), list1->data);
tail = tail->next;
list1 = list1->next;
list2 = list2->next;
} else if (list1->data < list2->data) {
list1 = list1->next;
} else {
list2 = list2->next;
}
}
return dummy.next;
}
int main() {
struct Node* list1 = NULL;
insert(&list1, 1);
insert(&list1, 2);
insert(&list1, 3);
struct Node* list2 = NULL;
insert(&list2, 2);
insert(&list2, 3);
insert(&list2, 4);
printf("List 1: ");
printList(list1);
printf("List 2: ");
printList(list2);
struct Node* intersection = findIntersection(list1, list2);
printf("Intersection: ");
printList(intersection);
return 0;
}
```
在上面的代码中,我们首先定义了一个 `Node` 结构来表示链表的节点。然后,我们使用 `insert` 函数将元素按升序插入链表中。最后,我们使用 `findIntersection` 函数来找到两个有序链表的交集,并使用 `printList` 函数打印结果。
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 # 返回合并后的链表的头节点
```