已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的交集新链表S3。 输入格式: 输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的交集序列,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。 输入样例: 1 2 5 -1 2 4 5 8 10 -1 输出样例: 2 5
时间: 2024-03-09 12:50:22 浏览: 97
下面是该题的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node *PtrToNode;
struct Node {
int data;
PtrToNode next;
};
PtrToNode createList();
void printList(PtrToNode head);
PtrToNode getIntersection(PtrToNode head1, PtrToNode head2);
int main() {
PtrToNode head1, head2, head3;
head1 = createList();
head2 = createList();
head3 = getIntersection(head1, head2);
if (head3 == NULL) {
printf("NULL");
} else {
printList(head3);
}
return 0;
}
// 创建链表
PtrToNode createList() {
int data;
PtrToNode head, tail, node;
head = tail = NULL; // 初始化头尾指针为空
scanf("%d", &data);
while (data != -1) {
node = (PtrToNode)malloc(sizeof(struct Node)); // 分配空间
node->data = data;
node->next = NULL;
if (head == NULL) {
head = node; // 空链表,新节点为头节点
} else {
tail->next = node; // 非空链表,新节点接在尾节点后
}
tail = node; // 更新尾节点
scanf("%d", &data);
}
return head;
}
// 输出链表
void printList(PtrToNode head) {
PtrToNode p = head;
while (p != NULL) {
printf("%d", p->data);
p = p->next;
if (p != NULL) {
printf(" ");
}
}
}
// 获取链表交集
PtrToNode getIntersection(PtrToNode head1, PtrToNode head2) {
PtrToNode head3, tail3, p1, p2, node;
head3 = tail3 = NULL;
p1 = head1;
while (p1 != NULL) {
p2 = head2;
while (p2 != NULL) {
if (p1->data == p2->data) {
node = (PtrToNode)malloc(sizeof(struct Node)); // 分配空间
node->data = p1->data;
node->next = NULL;
if (head3 == NULL) {
head3 = node; // 空链表,新节点为头节点
} else {
tail3->next = node; // 非空链表,新节点接在尾节点后
}
tail3 = node; // 更新尾节点
break; // 找到一个相同值,退出循环
}
p2 = p2->next;
}
p1 = p1->next;
}
return head3;
}
```
该代码实现中,使用了链表结构体`Node`,其中包含了一个整型数值`data`和一个指向下一个结点的指针`next`。通过`createList`函数创建两个链表`head1`和`head2`,分别表示输入的两个非降序序列。`getIntersection`函数用于获取两个链表的交集,返回一个新链表`head3`。在`getIntersection`函数中,通过两个指针`p1`和`p2`依次遍历两个链表,找到相同的结点后将其添加到新链表中。最后,通过`printList`函数输出新链表`head3`即可。