首页 > 代码库 > 链表相交以及找循环链表入口

链表相交以及找循环链表入口

链表相交需要判断有无循环,无循环直接找最后一个节点进行比较,有循环找某个循环点然后看看另一条是否也有这个点。

 

找循环链表入口比较牛逼:
在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再次重合的时候,必然是在链表的环路入口点上。

链表相交以及找循环链表入口