LeetCode刷题笔记 - 链表


141. Linked List Cycle

快慢指针,从头节点开始,一个慢指针一次走一步,一个快指针一次走两步,如果在快指针走到底前二者相遇,那么图里有环。

142. Linked List Cycle II

使用快慢指针判断是否有环,快慢指针相遇的点一定在环内。根据指针相遇的点和环的入口,我们可以将链表话分成三个部分:x,y,z。

Fast-slow pointers meet at "*"

|--------- x -----------|------ y  ------- \
_____________________________________      |
                     ---|            |     |
                      | |            |     |
                      | |            * ------
                      | |            |     |
                      | |____________|     |
                      |------- z ----------/

我们考虑快慢指针分别走过的长度

1. Slow = (x + y) + m(y + z)
2. Fast = (x + y) + n(y + z), n > m
3. Fast = 2  *slow

3. => 2 * ((x + y) + m(y + z)) = (x + y) + n(y + z)
   => x + y = (n - 2m) (y + z)
   let k = n - 2m
   => x + y = k(y + z)
   => x = k(y + z) -  y
   => x = (k - 1) (y + z) + z

由此可知,从x和z出发,每次走一步,则一定会在环入口相遇。这是因为从起点出发,走(k - 1) (y + z) + z步会到环入口,并且这是x第一次进入环;从快慢指针相遇的点出发,对任意p >= 0,走z + p(y + z)步都可以到环入口。由此可知,当p = k - 1时,x和z会相遇,且因为这是x第一次进入环,而z只在环内,x和z第一次相遇一定在环入口。