基于不引入回退概念应该容易理解一些
y总算法部分
(链表,快慢指针扫描) O(n)O(n)
本题的做法比较巧妙。
用两个指针 first,second分别从起点开始走,first 每次走一步,second 每次走两步。
如果过程中 second走到null,则说明不存在环。否则当 first 和 second 相遇后,让 first 返回起点,second 待在原地不动,然后两个指针每次分别走一步,当相遇时,相遇点就是环的入口。
证明部分
如图示,second指针比first指针跑的快一倍,即两者到达初次相遇点c时,first指针走过x + y,second指针走过2(x + y),也即second从b点入环后走过了x + 2y。又c点为从b点入环后距离y处,即环的周长或周长的倍数为x + y,所以此时让c点处的second指针继续向前走x步即可回到入环口b,而x步由first指针回到表头同步计步,即可在b点处相遇。
太清楚了,感谢!