一类由于值范围限定为正数进而有空间复杂度 O(1)的解法的算法题，如果不再限制值范围，还有没有可能空间复杂度 O(1)？

[Newyorkcity]

比如返回一个单向链表中的环的首节点（如果无环返回 null ）的算法题 如果节点的值的范围限定为正数 则可以原地取反的方式来判断该节点是不是已经访问过从而解题

就很想问下如果不限制值范围为正数，或者，只稍难一些，值范围是所有有效正数与零，

那还能不能获得空间复杂度 O(1)的解法呀？

https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

谢谢

[momocraft]

为什么原地取反可以知道是否访问过

[geelaw]

此题的标准做法是快慢指针

[kilasuelika]

@momocraft 值本来是正数，访问时取反变成负数。再读的时候看它是负数，那就是访问过了。

[Newyorkcity]

@geelaw ？请具体一点

[xiaopc]

首先这是 O(n) 的，其次牛客这道题下面的题解大部分都是快慢指针，也是 O(n) 的，具体看那些题解介绍得很清楚

[Newyorkcity]

@geelaw
@xiaopc

那除了这道题可以快慢指针外，这类题都可以吗。。比如返回数组中第一次重复的值的索引

[geelaw]

@Newyorkcity #4 提示“快慢指针”之后就应该自己搜索了。

#6 什么叫“这类”？
返回数组里第一次重复的索引本来就很自然地可以 O(1) 空间。

利用原来编码的冗余空间（比如这里是 32 位整数只用来表示 1 到 10000 ）的算法是比较作弊的方法，本质上还是（额外）空间 Omega(n) 的算法。