1 问题
输入两个链表，找出它们的第一个公共结点。
含有公共节点的两个链表的结构类似于下图中的链表：
1 -> 2 -> 3 -> 4 ->5
2 -> 4 ->5
可以看到两个链表中有一个公共节点，其中4节点就是这两个链表的公共节点
2 分析
既然题目是求公共节点，说明一定存在这个节点，然后我们可以发现两个链表的尾巴是一样，都重合了是Y性结构，我们先把长的链表的头移动到短的头那里，然后一个接着下一个比较就行
3 代码实现
#include <stdio.h> #include <stdlib.h> typedef 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; //这个地方不要忘记设置为NULL node->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; }
