### 题目

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

Follow up: Can you solve it without using extra space?

### 常规的遍历链表，时间复杂度 $O(n)$，空间复杂度 $O(n)$

#### 代码

/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
Set<ListNode> memo = new HashSet<>();
while (cur != null) {
if (cur.next != null && memo.contains(cur)) { return true; }
cur = cur.next;
}
return false;
}
}


### 把每个遇到过的节点的next节点都指向head，时间复杂度 $O(n)$，空间复杂度 $O(0)$

#### 代码

/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
if (head == null) { return false; }
while (cur != null) {
if (cur == head) { return true; }
ListNode temp = cur;
cur = cur.next;
}
return false;
}
}


### 夸父追日的故事，时间复杂度 $O(n)$，空间复杂度 $O(0)$

#### 代码

/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {