环型链表
题目描述：
给定一个链表，判断链表当中有没有环
解体思路：
思路一：
可以利用快慢指针的思路，给定两个指针，让两个指针一开始都位于链表头部的位置，然后开始走起来，一个指针每次走一步，一个指针每次走2步，如果说链表是有环的话，那么走的快的链表，就会先进入到环里面，然后一直在环里面绕圈圈，慢的指针也会一步一步走到环的里面，如果有环的话，那么最终两个指针一定是会相遇的，那么就可以通过快慢指针去判断链表里面到底有没有环。 代码如下所示：
class Solution {
public:
bool hasCycle(ListNode
*head
)
{
ListNode
*fast
=head
;
ListNode
*slow
=head
;
while(fast
&&fast
->next
)
{
fast
=fast
->next
->next
;
slow
=slow
->next
;
if(fast
==slow
)
return true;
}
return false;
}
};
还有一个问题需要去考虑------就是 快的指针走3步，慢的指针走一步可以吗？—答案是不可以的，因为如果快的指针和慢的指针的差值刚好是链表的长度的话，那么就算链表有环，快的指针和慢的指针也是不可能会相遇的，那么为什么要一个走一步，一个走两步呢？----因为链表中至少是要有一个结点的，而且1这个数字是可以被任意的数字所整除的。当两个指针都进入到环里面的时候，那么两个指针的之间的差值就是一直在缩小的，一直在缩小，那么到最后肯定是会相遇的。
快慢指针的复杂度分析
思路二：利用哈希表
哈希表法：每访问一个结点，检查该结点是否在哈希表中，如果在，则说明存在环，return true；否则，将该结点加入哈希表中。最终，若不存在环，遍历将结束，然后return false。就是看每个结点被访问的次数，一旦有一个结点被访问的次数是大于1的，那么这个链表就一定是存在环的
class Solution {
public:
bool hasCycle(ListNode
*head
)
{
unordered_map
<ListNode
*,int> ret
;
while(head
)
{
ret
[head
]++;
if(ret
[head
] > 1)
return true;
head
= head
->next
;
}
return false;
}
};
