### 题目

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

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

### 先确保用Map肯定能解

#### 代码

public class Solution {
if (head == null) { return null; }
Set<ListNode> memo = new HashSet<>();
while (cur != null) {
if (memo.contains(cur)) { return cur; }
cur = cur.next;
}
return null;
}
}


### 不使用额外空间

Linked List Cycle的启发，可以用一个walker指针，每次前进一格，一个runner指针，每次前移两格，先确定有没有cycle。

#### 代码

public class Solution {
if (head == null) { return null; }
// find cycle
ListNode mileStone = null;
while (runner.next != null && runner.next.next != null) {
runner = runner.next.next;
walker = walker.next;
if (runner == walker) {
mileStone = runner; // find the cycle, milestone must be one of the node in cycle
break;
}
}
if (mileStone == null) { return null; } // do not have cycle
ListNode cur = head, cycleCur = mileStone;
while (true) { // assert: must have cycle
do {
if (cur == cycleCur) { return cur; }
cycleCur = cycleCur.next;
} while (cycleCur != mileStone);
cur = cur.next;
}
}
}


### 天才的数学计算法

• 从起始节点到cycle的首个节点之间的距离是s步。
• 从cycle的首个节点到walkerrunner相遇的节点之间的距离为m步。
• cycle的周长为r步。

2k - k = nr (1式)（runner在遇到walker之前，已经绕着cycle跑了n圈了）

k = s + m (2式)（就是walker从起始点跑到和runner相遇的地方的距离，可以肯定walker没有跑完一圈）

s = nr - m (3式)

#### 代码

public class Solution {
if (head == null) { return null; }
// find cycle
ListNode mileStone = null;
int step = 0;
while (runner.next != null && runner.next.next != null) {
runner = runner.next.next;
walker = walker.next;
if (runner == walker) {
mileStone = runner; // find the cycle, milestone must be one of the node in cycle
break;
}
step++;
}
if (mileStone == null) { return null; } // do not have cycle
ListNode cur = head, cycleCur = mileStone;
while (cur != cycleCur) {
cur = cur.next;
cycleCur = cycleCur.next;
}
return cur;
}
}