用C语言编写算法求两个单链表的公共结点,使用的方法是先在第一个链表顺序遍历每一个节点,每遍历一个节点,在第二个链表上顺序遍历所有结点,直到找到所有公共节点
时间: 2024-12-06 15:22:44 浏览: 21
C语言实现输出链表中倒数第k个节点
5星 · 资源好评率100%
在C语言中,我们可以采用双指针法来解决这个问题。假设我们有两个单链表`list1`和`list2`,我们需要找到它们之间的公共结点。以下是简单的步骤:
1. 定义两个指针`p1`和`p2`,分别初始化为`list1`和`list2`的头节点。
2. 使用循环遍历,同时移动两个指针:
- 如果`p1`为空或`p1->next`为空(即`list1`遍历结束),说明`list2`中没有对应的公共结点,返回空或结束查找。
- 同样地,如果`p2`为空或`p2->next`为空(`list2`遍历结束),将`p1`移到下一个节点继续检查。
- 比较当前`p1`和`p2`指向的节点,如果地址相等,则找到了一个公共结点,将其记录下来(如存储到数组或临时结构体中),然后都向后移动一个节点。
- 继续这个过程,直到其中一个链表遍历完。
3. 返回找到的所有公共结点。
下面是一个简化的伪代码示例:
```c
struct ListNode* findCommonNodes(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* p1 = list1;
struct ListNode* p2 = list2;
while (p1 && p2) {
if (p1 == p2) {
// 找到公共结点,添加到结果列表或其他数据结构中
common_nodes.push_back(p1);
}
if (p1->next) {
p1 = p1->next;
} else {
p1 = NULL; // list1遍历结束
}
if (p2->next) {
p2 = p2->next;
} else {
p2 = NULL; // list2遍历结束
}
}
return common_nodes; // 或者直接返回找到的公共结点
}
```
阅读全文