力扣141-环形链表

发布时间 2023-12-16 17:16:30作者: metasequoiaa

难度:【简单】

第一遍:用最朴素的算法写,一个HashSet保存访问过的节点,但是仅保存了节点的value,出现值相等的节点算法就会失效。提交后当然是“解答错误”。

第二遍:修改HashSet数据类型,重新提交后显示“通过”。

第三遍:优化空间复杂度到O(1)。没有思路就参考了官方题解,使用了快慢指针。自己写的时候,想当然的认为“一个指针在前一个指针在后罢了”,运行一下报错“超时”。改了一下快指针的步长,运行结果才对了。为什么两个指针一个每次移动一步,一个每次移动两步呢?可以预设一下两个指针移动步长相等的情况:一前一后,两个指针的距离始终不变,即使有环两个指针也无法相遇,循环无法终止。只有“一个移动得快,一个移动得慢”,两个指针才有可能相遇,这才是所谓的“快慢指针”,一个跑得快一个跑得慢。