1.我想到的用set。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { unordered_set<ListNode*> us; while(head!=NULL){ if(us.find(head)==us.end()) us.insert(head); else return true; head=head->next; } return false; } };
2. 双指针，不使用额外空间。
一个速度为2，一个速度为1。
https://blog.csdn.net/nomasp/article/details/51598735
作者没给出证明。我的证明如下：
node == n
car = (2i+1) //%n
man= i //%n
Q:car-man==k*n ？
=>
i+1 evenly divide n
yes
车速度为2，人速度为1.
如果有环，他们离得最近的时候可能相遇，如果不，那么相差1.
设车、人坐标为……
Q：坐标之差可能为环的整数倍吗？
可以，i+1可以==n
代码思路：
车前进2，人前进1.
if 坐标相等，true
if car==NULL || car->next ==NULL , false
不判断人，因为车比人快，已经判断过了。
还有，同一行定义两个指针：
ListNode *i , *j ;
转载于:https://www.cnblogs.com/azureice/p/leetcode141.html
