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

时间: 2023-05-29 13:04:49 浏览: 117

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

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

#include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node* next; } Node; Node* createLinkedList(int n); void printLinkedList(Node* head); int getLength(Node* head); Node* findFirstCommonNode(Node* head1, Node* head2); int main() { int n1, n2; scanf("%d", &n1); Node* head1 = createLinkedList(n1); scanf("%d", &n2); Node* head2 = createLinkedList(n2); Node* commonNode = findFirstCommonNode(head1, head2); int count = 0; while (commonNode != NULL) { count++; commonNode = commonNode->next; } printf("%d\n", count); commonNode = findFirstCommonNode(head1, head2); while (commonNode != NULL) { printf("%d ", commonNode->value); commonNode = commonNode->next; } return 0; } Node* createLinkedList(int n) { Node* head = NULL; Node* current = NULL; for (int i = 0; i < n; i++) { int value; scanf("%d", &value); Node* node = (Node*) malloc(sizeof(Node)); node->value = value; node->next = NULL; if (head == NULL) { head = node; current = node; } else { current->next = node; current = node; } } return head; } void printLinkedList(Node* head) { while (head != NULL) { printf("%d ", head->value); head = head->next; } printf("\n"); } int getLength(Node* head) { int length = 0; while (head != NULL) { length++; head = head->next; } return length; } Node* findFirstCommonNode(Node* head1, Node* head2) { int length1 = getLength(head1); int length2 = getLength(head2); if (length1 > length2) { for (int i = 0; i < length1 - length2; i++) { head1 = head1->next; } } else { for (int i = 0; i < length2 - length1; i++) { head2 = head2->next; } } while (head1 != NULL && head2 != NULL && head1 != head2) { head1 = head1->next; head2 = head2->next; } return head1; }

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

阅读全文

相关推荐

已知单链表L为按值递增有序的，编写算法将数据元素值在区间[e1,e2]内的所有结点取出建立一个新单链表L1

算法：给定一个链表，判断链表中是否存在环

链表的概念、链表的优势、链表的c语言和java语言的实现

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

单链表 单链表 单链表 链表

问题描述： 给定一个头结点为head的非空单链表，返回链表的中间结点。如果有两个中间节点，则返回第二个中间结点。 例如：程序输入： 1 2 3 4 5 程序输出： 3 用c语言作答

用C语言 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的

用c语言写出将链表逆置的算法：给定一个带头结点的链表L，每个结点数据成员包括int data，Lnode *next

已知二叉树采用二叉链表存储结构，指向根结点存储地址的指针为t，是编写一算法，判断该二叉树是否为完全二叉树 C语言编写程序

已知二叉树采用二叉链表结构，用C语言编写完整的算法，输出结点b的双亲。

如何用C语言编写一个算法，基于给定的单链表数据结构，首先创建该链表，然后删除所有值在emin和emax范围之外的节点？请提供必要的数据结构定义和相应的代码实现步骤。

设二叉树为以二叉链表为存储结构，且树中结点的关键字均不同。用c语言编写算法，判别给定二叉树是否为二叉排序树

设T是一棵给定的数，试用C语言编写一个在数T中删除结点值为a的子树的程序，这里假设树T中的结点采用二叉链表存储结构

c语言设计结构 给定一个带头结点的单链表,设计算法按递增次序输出单链表中各结点的数据元素,并释放结点所占的存储空间。

建立带头结点的单链表，试编写算法，在第i个位置前插入一个新元素，在第j个位置删除一个元素用C语言编写，并解释代码含义

用c语言算法实现在长度大于1的循环单链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，要求删除结点s的前趋结点

spring-boot-2.3.0.RC1.jar中文-英文对照文档.zip

presto-jdbc-0.238.1.jar中文文档.zip

大家在看

0132、单片机-485-PC串口通信proteus仿真+程序资料.zip

VBA加密工具,将DVB文件错位加密

WebServerApp

Cluster Load Balance Algorithm Simulation Based on Repast

Tibco Document

最新推荐

spring-boot-2.3.0.RC1.jar中文-英文对照文档.zip

presto-jdbc-0.238.1.jar中文文档.zip

Linux_SID_开发指南.pdf

实现Struts2+IBatis+Spring集成的快速教程

【数据融合技术】：甘肃土壤类型空间分析中的专业性应用

Waymo使用稀疏图卷积处理LiDAR点云，目标检测精度提升15%

Dwr实现无刷新分页功能的代码与数据库实例

【空间分布规律】：甘肃土壤类型与农业生产的关联性研究

缓存延迟双删的实际解决方案通常怎么实现

企业内部文档管理平台使用Asp.net技术构建

单链表单链表单链表链表

问题描述：给定一个头结点为head的非空单链表，返回链表的中间结点。如果有两个中间节点，则返回第二个中间结点。例如：程序输入： 1 2 3 4 5 程序输出： 3 用c语言作答

用C语言将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的

c语言设计结构给定一个带头结点的单链表,设计算法按递增次序输出单链表中各结点的数据元素,并释放结点所占的存储空间。