链表--环形链表

目录

环形链表一

思路

    使用快慢指针，在无环的情况下，快指针一定先到达链表尾，否则，快慢指针将最终在环内一直循环下去，但总有一个时间点会相遇

实现

环形链表二

思路

    由上一题可知，存在环时，l和r一定会在某一点相遇

    由于我们每次让r的移动距离是l的两倍，故两点在相遇时，r走过的总距离也为l的两倍

    则如图

    l走过的距离为：a+b

    r走过的距离为：a+n(b+c)+b

    根据距离关系，可知

        2(a+b) = a+n(b+c)+b

        则

        a=c+(n−1)(b+c)

    即

        a=c

    则当两点相遇时，a从head出发，c从r触发，两点将在入环处相遇

实现