目录链接：//www.greatytc.com/p/9c0ada9e0ede
环形链表
环形链表(Linked List Cycle)
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
</pre>
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
切题
一、Clarification
本题没有什么需要注意的边界条件，目标也很简单判断链表是否成环
二、Possible Solution
1、存储记录
这应该是比较容易想到的，将我们遍历的节点记录下来，然后每次新节点都看它是否已经被记录，如果没有就将其记录下来，如果有表示链表成环，如果到了链表末尾到没有重复记录表示链表没有环
python的话可以用set来记录节点，其时间复杂度为 O(n)
2、快慢指针
两个指针循环遍历链表，慢指针每次循环移一步快指针每次循环移两步，如果链表遍历结束之前存在快慢指针指向同一节点则链表成环,如果快或慢指针到达链表结尾且没相遇表示链表无环，其时间复杂度为 O(n)
Python3 实现
1、存储记录 实现 Py3
环形链表(Linked List Cycle) Py3 存储记录 实现
# @author:leacoder
# @des: 存储记录 环形链表
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
save = set() #用于 存储 链表中每个节点地址
cur = head
while cur is not None: #循环迭代链表
if cur in save: #是否有记录
return True #有返回True
else:
save.add(cur) #存储记录cur
cur = cur.next #下移
return False
2、快慢指针 实现 Py3
环形链表(Linked List Cycle) Py3 快慢指针 实现
# @author:leacoder
# @des: 快慢指针 环形链表
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast = slow = head
while fast.next:
slow = slow.next #慢指针 每次移一步
fast = fast.next.next #快指针 每次移二步
if slow == fast:
return True
return False
Java实现
Java实现逻辑上与Python3无区别
1、存储记录 实现 Java
环形链表(Linked List Cycle) Java 存储记录 实现
2、快慢指针 实现 Java
环形链表(Linked List Cycle) Java 快慢指针 实现
C++实现
环形链表(Linked List Cycle) C++ 快慢指针 实现
扩展阅读：
Python3 集合
Python Data Structures
Java 集合框架
Java HashSet api doc from oracle
HashSet 的实现原理
GitHub链接：
https://github.com/lichangke/LeetCode
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习
