用c语言编写程序 找出两个链表的公共结点 【问题描述】给定两个单链表,编写算法找出两个链表的公共结点。 【输入形式】 四行: 第一行:一个数字(第一个单链表中的元素个数) 第二行:第一个单链表中各个结点的值 第三行:一个数字(第二个单链表中的元素个数) 第四行:第二个单链表中各个结点的值 【输出形式】 两行: 第一行:两个单链表的公共元素个数 第二行:依次打印输出各个公共元素 【样例输入】 6 12 5 8 9 -23 16 4 16 21 9 3 【样例输出】 2 9 16 注:若两个链表无公共元素,则输出: 0 没有公共元素
时间: 2023-05-29 15:05:12 浏览: 69
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct Node {
int data;
struct Node *next;
} Node;
// 创建链表
Node* createList(int n) {
Node *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
Node *node = (Node*)malloc(sizeof(Node));
scanf("%d", &node->data);
node->next = NULL;
if (tail == NULL) {
head = tail = node;
} else {
tail->next = node;
tail = node;
}
}
return head;
}
// 遍历链表
void traverseList(Node *head) {
Node *p = head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 获取链表长度
int getListLength(Node *head) {
int len = 0;
Node *p = head;
while (p != NULL) {
len++;
p = p->next;
}
return len;
}
// 找到两个链表的公共节点
Node* findCommonNode(Node *head1, Node *head2, int *count) {
int len1 = getListLength(head1);
int len2 = getListLength(head2);
Node *p1 = head1;
Node *p2 = head2;
// 将两个链表的长度调整为相等
if (len1 > len2) {
for (int i = 0; i < len1 - len2; i++) {
p1 = p1->next;
}
} else {
for (int i = 0; i < len2 - len1; i++) {
p2 = p2->next;
}
}
// 查找公共节点
Node *common = NULL;
while (p1 != NULL && p2 != NULL) {
if (p1->data == p2->data) {
if (common == NULL) {
common = p1;
}
(*count)++;
} else {
common = NULL;
*count = 0;
}
p1 = p1->next;
p2 = p2->next;
}
return common;
}
int main() {
int n1, n2;
scanf("%d", &n1);
Node *head1 = createList(n1);
scanf("%d", &n2);
Node *head2 = createList(n2);
int count = 0;
Node *common = findCommonNode(head1, head2, &count);
if (common == NULL) {
printf("0 没有公共元素\n");
} else {
printf("%d ", count);
while (common != NULL) {
printf("%d ", common->data);
common = common->next;
}
}
return 0;
}