判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。
比较好的方法有两个:
一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。
二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。
这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。
注释1
设r为环长,则fast指针r/2内可以跑完一圈,若r为奇数,刚r步内fast会遍历循环内所有点.刚r内一定会跟slow相遇.若r为偶数,r/2步内可令fast跟slow的最近距离为2或1(f追赶s).若为2,则
fast+2=slow
所以下一步时slow的位置是slow+1;而fast则为fast+2;
再下步slow+2,fast+4;
因为之前fast+2=slow,所以
slow-2+4=slow+2
又因为最近距离为1时,只要两指针各走一步便相遇.
所以两指针相遇.最大步数为s<=r/2+2(r>=4)
分享到:
相关推荐
8.判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
直线相交容易判断,但判断两条线段是否相交有些困难,本代码不但能判断是否相交,还能求出交点坐标。
判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? 9.判断两个单链表是否相交 10.两个单链表相交,计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素
给出两个单向链表的头指针(如图3-8 所示),比如h1、h2,判断这两个链表是否 相交。这里为了简化问题,我们假设两个链表均不带环。
Unity3D判断两个物体相交脚本 Posted on 2013年02月25日 by U3d / Unity3D脚本/插件/被围观 285 次 Unity3D中
编程实现了如何判断一个平面里的两条线段是否相交!
分析与解法 这样的一个问题,也许我们平时很少考虑。但在一个大的系统中,如果出现两个链表相 交的情况,而且释放了其中一个链表的...的两个链表,我们希望在释放一个链表之前知道是否有其他链表跟当前这个链表相交。
(1)定义一个Point类,其属性包括点的坐标,提供计算两点之间距离的方法; (2)定义一个圆形类,其属性包括圆心和半径;...(3)创建两个圆形对象,提示用户输入圆心坐标和半径,判断两个圆是否相交,并输出结果。
判断通过空间的坐标点确定的选段是否相交,相交的求出交点
实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....
用VC6.0实现的MFC单文档程序,用鼠标在屏幕上任意画两条直线,判断两直线是否相交。
判断任意位置旋转的矩形是否相交,相交输出true,否则输出false。
1.3.9 如何判断两个链表是否相交
geotools 判断几何要素的交点 当时想到用的GDAL 但是 交点函数返回的对象总是null , 改用 GeoTools 这个库,需要用到jar 到官网上下载,主要是jts-core-1.16.0.jar
判断两个有环链表是否相交,相交则返回第一个相交节点,否则返回null 在考虑此问题时,根据前面几篇文章的解法,我们已经得到了各自链表的入环节点,分别为loop1和loop2 思路 以下是问题三的具体解决过程: 如果loop...
创建两个圆形对象,提示用户输入圆心坐标和半径,判断两个圆是否相交,并输出结果。 方法:定义一个Point类,其属性包括点的坐标,提供计算两点之间距离的方法;定义一个Circl类,其属性包括圆心和半径。
perl 依四点的坐标,判断两线段是否相交,若相交求出交点。
这个方法很简单,几句就可以,经过本人呕心沥血思考,终于想出这么简单的两句判断直线相交,真心了不起直线相交,真心了不起直线相交,真心了不起
算法分析中判断两线段是否相交问题,提供相关的代码