给定两个单链表,编写一个找出两个链表的公共结点(用c语言)
时间: 2024-11-15 20:27:33 浏览: 15
算法:给定一个链表,判断链表中是否存在环
在C语言中,你可以通过遍历两个链表并比较节点的方式来找到它们的公共节点。这里是一个简单的算法实现步骤:
1. 首先,分别创建两个指针,`p1` 和 `p2`,分别指向两个链表的头节点。
2. 然后,同时开始遍历这两个链表,每次移动一步,直到其中一个链表结束。如果某个时刻两个指针都未到达链表尾部,并且他们指向的节点值相等,那么这个节点就是公共节点。当其中一个指针到达尾部,说明另一个链表中没有相同的节点,那么就停止遍历。
以下是伪代码形式的实现:
```c
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; // 没有公共节点的情况
}
```
阅读全文