美文网首页
寻找链表中环的起始位置

寻找链表中环的起始位置

作者: Jiafu | 来源:发表于2017-09-29 15:20 被阅读0次

    解法如下:
    定义两个指针:p1和p2,当p2按照每次2步,p1每次一步的方式走,发现p2和p1重合,确定了单向链表有环路了。
    接下来,让p2回到链表的头部,重新走,每次步长不是走2了,而是走1,那么当p1和p2再次相遇的时候,就是环路的入口了。
    这点可以证明的:
    在p2和p1第一次相遇的时候,假定p1走了n步骤,环路的入口是在p步的时候经过的,那么有
    p1走的路径: p+c = n; c为p1和p2相交点,距离环路入口的距离
    p2走的路径: p+c+kL = 2N; L为环路的周长,k是整数
    显然,如果从p+c点开始,p1再走n步骤的话,还可以回到p+c这个点
    同时p2从头开始走的话,经过n步,也会达到p+c这点
    显然在这个步骤当中p1和p2只有前p步骤走的路径不同,所以当p1和p2再次重合的时候,必然是在链表的环路入口点上。

    相关文章

      网友评论

          本文标题:寻找链表中环的起始位置

          本文链接:https://www.haomeiwen.com/subject/qhmiextx.html