Given a linked list, determine确定 if it has a cycle in it.
To represent代表 a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.Follow up:
Can you solve it using O(1) (i.e. constant常数的空间复杂度) memory?
硬做，限定时间，看最后一个是否是空指针，假如是空，就认为无环。
我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表存储已经访问过的元素。
我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。
复杂度：
时间复杂度为O(n)，对于有n个元素的链表，访问每个元素最多一次，添加一个节点到哈希表中只需要花费O(1)的时间
空间复杂度为O(n)，空间取决于添加到哈希表中元素数目，最多需要添加n个元素
双指针方法：想象一下，两名运动员以不同的速度在环形赛道上跑步会发生什么？
算法
通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。
如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。
现在考虑一个环形链表，把慢指针和快指针想象成两个在环形赛道上跑步的运动员（分别称之为慢跑者与快跑者）。而快跑者最终一定会追上慢跑者。这是为什么呢？
考虑下面这种情况（记作情况 A）- 假如快跑者只落后慢跑者一步，在下一次迭代中，它们就会分别跑了一步或两步并相遇。
其他情况又会怎样呢？例如，我们没有考虑快跑者在慢跑者之后两步或三步的情况。但其实不难想到，因为在下一次或者下下次迭代后，又会变成上面提到的情况 A。
可以得知，时间复杂度为O(n)；空间复杂度为O(1)，因为只用了快慢指针两个节点。
public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; }