第7 题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针,比如h1,h2,判断这俩个链表是否相交。
为了简化问题,我们假设俩个链表均不带环。
问题扩展:
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct node {
int value;
node *next;
};
/**
* 是否有环
*/
bool check(node* head) {
if (head == NULL)
return false;
node *low = head, *fast = head -> next;
while (fast != NULL && fast -> next != NULL) {
low = low -> next;
fast = fast -> next -> next;
if(low == fast)
return true;
}
return false;
}
/**
* 获取尾结点
*/
node* lastNode(node* head) {
if (head == NULL)
return NULL;
node* node = head;
while (node -> next != NULL) {
node = node -> next;
}
return node;
}
int main() {
node *p1, *p2, *p2_2;
p2_2 = (node*) malloc(sizeof(node));
p2 -> value = 22;
p2_2 -> next = NULL;
p1 = (node*) malloc(sizeof(node));
p1 -> value = 1;
p1 -> next = p2_2;
p2 = (node*) malloc(sizeof(node));
p2 -> value = 2;
p2 -> next = p2_2;
if (check(p1) || check(p2)) { // 有环
while (p1 != p2 && p1 != NULL && p2 != NULL) {
p1 = p1->next;
if (p2->next)
p2 = p2->next->next;
else
p2 = p2->next;
}
if (p1 == p2 && p1 && p2)
printf("相交");
else
printf("不相交");
} else { // 无环
if (lastNode(p1) == lastNode(p2))
printf("相交");
else
printf("不相交");
}
printf("\nPress any key to end");
getch();
return 0;
}
分享到:
相关推荐
04.单向链表以及单向链表的应用.ppt
给出两个单向链表的头指针(如图3-8 所示),比如h1、h2,判断这两个链表是否 相交。这里为了简化问题,我们假设两个链表均不带环。
分析与解法 这样的一个问题,也许我们平时很少考虑。但在一个大的系统中,如果出现两个链表相 交的情况,而且释放了其中一个链表的...的两个链表,我们希望在释放一个链表之前知道是否有其他链表跟当前这个链表相交。
将一个单向链表反向连接
1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)...利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
1.3.9 如何判断两个链表是否相交
简易链表linux下实现单向链表的C语言实现程序,有详尽的链表操作函数,可以作为C语言学习的参考代码
删除链表的倒数第N个节点、面试题02.07.链表相交和142.环形链表II。记录了清晰的文字题解+图示以及Java参考代码。 适合人群:链表算法感兴趣的程序员或学生,想要打好数据结构与算法基础的人。 能学到什么:掌握链表...
C#单向链表的实现的源码
可以看到如果把h1链表的尾节点的next指针指向h2链表的第一个节点,那么可以看到如果h1和h2相交,则h2变成了一个循环单链表,因此只需判断h2是否为循环链表
21. 合并两个有序链表瞎写的不带头结点的方法def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> Li
单向链表架构代码,适合学习链表的学生学习!内附排序函数,打印函数,链表尾添项函数,删除函数。
单向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材
这是一个单向链表,它具有插入与删除节点的功能。Entry类实现了链表的各节点。
c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
slist.h为单向链表,blist为双向链表
一个抽象链表类的C++模板实现,主要适合初学者入门数据结构基础。