链表 若单链表存在环 如何找到环的入口点（链表插入和删除示意图）

比较简单的证明方法是考虑从头节点开始向下走的序列，在单链表节点数量不超过N的时候，它要么在有限步内结束，要么在有限步内出现重复的节点，因为单链表的下一个节点是唯一的，因此序列有固定的循环周期。当单链表不循环时，快慢指针显然不会相遇，只考虑循环的情况。

设序列为A[n]，且从A[i]开始，对于任意m>=i有A[m+T]=A[m]，其中T>=1。我们只需要证明存在k，使得A[2k] = A[k]即可。任取一个使得uT>=i的u，令k=uT，则有A[2uT] = A[uT + uT] = A[uT + (u-1)T] = ... = A[uT]，即A[2k] = A[k]，命题得证