c语言的数据结构:找环状链表入口处

一起<(￣︶￣)↗[GO!]

1.如何判断一个链表是否有环

思路:设定两个快慢指针fast和slow,fast每次走两个结点,slow每次走一个节点

如果fast指针遇到了Null,那么这个链表没有环,如果fast和slow可以相遇,则代表这个链表有环

代码如下

N:fast先进环,slow后进环,fast和slow之间的距离是N

N--->偶数--->奇数

          N           N

          N-2       N-2

         N-4        N-4

         ...             ...

           4              3

           2              1

           0              -1

       追上了           过了,进入下一个循环(fast超过slow1个结点了)

                             C:圆环的周长 

                             slow和fast之距变为c-1

                             c-1是偶数,下一轮便追上了

                             c-1是奇数,那么永远也追不上

2.找环的入口点

追上相遇时

1.slow所走距离:L+X

2.fast所走距离:L+X+N*C

3.追上之后相关结论推导

2(L+X)= L+X+N*C

为何是2*slow距离=fast之距离?

答:等式两边的表达式实际上是二者所走过的距离.由物理公式X=VT可知,因为是同时运行,时间(循环次数)相同,所以"T"可以约掉,仅有2*Vfast=Vslow;

L+X=N*C      L=N*C-X;

有 L=(N-1)*C+C-X;

得出重要结论:一指针从链表头开始走,

另一指针从相遇点开始走,

则牠们会在入口点相遇

3.代码

思路:1. 先判断是否有环

        2.再让slow和fast相遇,以找到meet点

        3.让head和meet以每循环1结点的速度同向运动,二者相遇之时便是找到入口点之时