问题：

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

解决：

① 采用快慢指针，fast每次前进2步，slow每次前进1步，若两者相遇，则说明存在环。若fast指向null或者fast的下一个是null，就说明没有环。

/**

 * Definition for singly-linked list.  * class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */

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; }

② 使用hash set存储已经遍历过的节点，若有重复，说明存在环，否则不存在。

public boolean hasCycle(ListNode head) {

    Set<ListNode> nodesSeen = new HashSet<>();     while (head != null) {         if (nodesSeen.contains(head)) {             return true;         } else {             nodesSeen.add(head);         }         head = head.next;     }     return false; }