用c语言编写程序找出两个链表的公共结点 【问题描述】给定两个单链表，编写算法找出两个链表的公共结点。 【输入形式】 四行： 第一行：一个数字（第一个单链表中的元素个数） 第二行：第一个单链表中各个结点的值 第三行：一个数字（第二个单链表中的元素个数） 第四行：第二个单链表中各个结点的值 【输出形式】 两行： 第一行：两个单链表的公共元素个数 第二行：依次打印输出各个公共元素 【样例输入】 6 12 5 8 9 -23 16 4 16 21 9 3 【样例输出】 2 9 16 注：若两个链表无公共元素，则输出： 0 没有公共元素

//链表结构体
typedef struct ListNode{
int val;
struct ListNode* next;
}ListNode;

int getLength(ListNode* head){ //求链表长度
int len = 0;
while(head != NULL){
len++;
head = head->next;
}
return len;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = getLength(headA);
int lenB = getLength(headB);
//将两个链表长度对齐，长的链表先走差值步
while(lenA > lenB){
headA = headA->next;
lenA--;
}
while(lenB > lenA){
headB = headB->next;
lenB--;
}
//同时遍历两个链表，找到第一个相同的结点
while(headA != NULL && headB != NULL){
if(headA == headB)
return headA;
headA = headA->next;
headB = headB->next;
}
return NULL; //没有公共结点
}

int main(){
int n1, n2;
scanf("%d", &n1);
ListNode* head1 = (ListNode*)malloc(sizeof(ListNode));
ListNode* p1 = head1;
for(int i = 0; i < n1; i++){
int x;
scanf("%d", &x);
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = x;
node->next = NULL;
p1->next = node;
p1 = p1->next;
}
scanf("%d", &n2);
ListNode* head2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* p2 = head2;
for(int i = 0; i < n2; i++){
int x;
scanf("%d", &x);
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = x;
node->next = NULL;
p2->next = node;
p2 = p2->next;
}
ListNode* intersection = getIntersectionNode(head1->next, head2->next);
if(intersection == NULL){
printf("0 没有公共元素");
}
else{
int cnt = 0;
while(intersection != NULL){ //计算公共元素个数
cnt++;
intersection = intersection->next;
}
printf("%d ", cnt);
intersection = getIntersectionNode(head1->next, head2->next);
while(intersection != NULL){ //打印公共元素
printf("%d ", intersection->val);
intersection = intersection->next;
}
}
return 0;
}