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

思路：

先遍历两个链表，找出它们的长度 $len1$ 和 $len2$，以及它们的尾结点 $tail1$ 和 $tail2$。如果尾结点不同，说明两个链表没有公共结点，直接输出结果即可。如果尾结点相同，说明两个链表有公共结点，接下来可以利用双指针法，将两个链表的头结点对齐，然后同时向后遍历，直到找到第一个相同的结点为止。

代码实现：

相关问题

用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;
}

给定两个单链表，编写一个找出两个链表的公共结点（用c语言）

在C语言中，你可以通过遍历两个链表并比较节点的方式来找到它们的公共节点。这里是一个简单的算法实现步骤：

1. 首先，分别创建两个指针，`p1` 和 `p2`，分别指向两个链表的头节点。

2. 然后，同时开始遍历这两个链表，每次移动一步，直到其中一个链表结束。如果某个时刻两个指针都未到达链表尾部，并且他们指向的节点值相等，那么这个节点就是公共节点。当其中一个指针到达尾部，说明另一个链表中没有相同的节点，那么就停止遍历。

以下是伪代码形式的实现：

struct ListNode* findCommonNode(struct ListNode* head1, struct ListNode* head2) {
    struct ListNode *p1 = head1;
    struct ListNode *p2 = head2;

    while (p1 && p2) {
        if (p1->val == p2->val) {
            return p1; // 如果找到相等节点，返回它
        }
        if (p1->next) {
            p1 = p1->next;
        } else {
            break; // 当链表1遍历完还没找到，说明链表2有该节点
        }
        if (p2->next) {
            p2 = p2->next;
        } else {
            break; // 同理，当链表2遍历完还没找到，说明链表1有该节点
        }
    }

    return NULL; // 没有公共节点的情况
}