首页 > 代码库 > 链表相交以及找循环链表入口
链表相交以及找循环链表入口
链表相交需要判断有无循环,无循环直接找最后一个节点进行比较,有循环找某个循环点然后看看另一条是否也有这个点。
找循环链表入口比较牛逼:
在p2和p1第一次相遇的时候,假定p1走了n步,环路的入口是在h步的时候经过的,那么有
p1走的路径: h+c = n; c为p1和p2相交点,距离环路入口的距离
p2走的路径: h+c+k*r = 2*n; r为环路的周长,k是整数
显然,如果从h+c点开始,p1再走n步骤的话,还可以回到h+c这个点
同时p2从头开始走的话,经过n步,也会达到h+c这点
显然在这个步骤当中p1和p2只有前h步走的路径不同,所以当p1和p2再次重合的时候,必然是在链表的环路入口点上。
链表相交以及找循环链表入口
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。