苏州网站建设招标,用jsp进行网站开发,wordpress高端,抖音小程序官网1 问题
输入两个链表#xff0c;找出它们的第一个公共结点。
含有公共节点的两个链表的结构类似于下图中的链表#xff1a;
1 - 2 - 3 - 4 -5 2 - 4 -5
可以看到两个链表中有一个公共节点#xff0c;其中4节点就是这两个链表的公共节点 2 分析…1 问题
输入两个链表找出它们的第一个公共结点。
含有公共节点的两个链表的结构类似于下图中的链表
1 - 2 - 3 - 4 -5 2 - 4 -5
可以看到两个链表中有一个公共节点其中4节点就是这两个链表的公共节点 2 分析
既然题目是求公共节点说明一定存在这个节点然后我们可以发现两个链表的尾巴是一样都重合了是Y性结构我们先把长的链表的头移动到短的头那里然后一个接着下一个比较就行 3 代码实现
#include stdio.h
#include stdlib.htypedef struct Node
{int value;struct Node *next;
} Node;/** 初始化结构体*/
struct Node* init(struct Node *node, int value)
{node (struct Node*)malloc(sizeof(Node));if (node ! NULL){node-value value;//这个地方不要忘记设置为NULLnode-next NULL;return node;}return NULL;
}/** 获取链表的长度*/
int length(Node *head)
{if (head NULL)return 0;Node *p head;int length 0;while (p ! NULL){length;p p-next;}return length;
}/*** 找到第一个公共的节点*/
struct Node* get_common(Node *head1, Node *head2)
{if (head1 NULL || head2 NULL){return NULL;}int list1_length length(head1);int list2_length length(head2);Node *short_head NULL;Node *long_head NULL;int sub_len 0;if (list1_length list2_length){short_head head2;long_head head1;sub_len list1_length - list2_length;}else{short_head head1;long_head head2;sub_len list2_length - list1_length;}//移动长链表确保两个链表一样长while (sub_len 0){sub_len--;long_head long_head-next;}while (short_head ! NULL long_head ! NULL){if (short_head-value long_head-value){return short_head;}short_head short_head-next;long_head long_head-next;}return NULL;
}int main()
{Node *n1 NULL;Node *n2 NULL;Node *n3 NULL;Node *n4 NULL;Node *n5 NULL;Node *m1 NULL;Node *m2 NULL;Node *m3 NULL;n1 init(n1, 1);n2 init(n2, 2);n3 init(n3, 3);n4 init(n4, 4);n5 init(n5, 5);m1 init(m1, 2);m2 init(m2, 4);m3 init(m3, 5);if (n1 n2 n3 n4 n5){n1-next n2;n2-next n3;n3-next n4;n4-next n5;}if (m1 m2 m3){m1-next m2;m2-next m3;}Node *node get_common(n1, m2);if (node){printf(common node value is: %d\n, node-value);}else{printf(two list do not common value\n);}if (n1) {free(n1); n1 NULL;}if (n2) {free(n2); n2 NULL;}if (n3) {free(n3); n3 NULL;}if (n4) {free(n4); n4 NULL;}if (n5) {free(n5); n5 NULL;}if (m1) {free(m1); m1 NULL;}if (m2) {free(m2); m1 NULL;}if (m3) {free(m3); m1 NULL;}return 1;
} 4 运行结果
common node value is: 4 5 总结
如果我们求链表的长度一般是这样的函数
/** 获取链表的长度*/
int length(Node *head)
{if (head NULL)return 0;Node *p head;int length 0;while (p ! NULL){length;p p-next;}return length;
}
一定要记到骨髓里面去。
