# Linked List Cycle II

## Question

### Description

Given a linked list, return the node where the cycle begins.

If there is no cycle, return`null`.

### Example

Given`-21->10->4->5`, tail connects to node index 1，return`10`

### Challenge

Can you solve it without using extra space?

## 题解思路

``````    a            b
A ------ B --------+
|         |
c |         |
+-------- C

* A: 起始点
* B: Cycle Begins
* C: 1st 快慢指针相遇点

* A->B: a
* B->C: b
* C->B: c
* 环的长度 (b+c) 为 R
``````

a + b

a + b + nR

2(a + b) = a + b + nR

a + b = nR

b + c = R

a = (n - 1)R + c;

## 源代码

Easier to understand:

``````/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
while (slow != null && fast != null) {
slow = slow.next;
if (fast.next == null) return null;
fast = fast.next.next;
if (slow == fast) break;
}
if (fast != null) {
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
return null;
}
}
``````

Preferred Implementation:

``````/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
private ListNode answer = null;
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
ListNode slow = head;
ListNode fast = head;

while(fast != null && fast.next != null) {

slow = slow.next;
fast = fast.next.next;

if (slow == fast) {
break;
}
}
if (fast == slow) {
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
return null;
}
}
``````

Harder to understand with pointer corner cases

``````/**
* Definition for ListNode.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int val) {
*         this.val = val;
*         this.next = null;
*     }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next==null) {
return null;
}

ListNode fast, slow;
while (fast != slow) {
if(fast==null || fast.next==null)
return null;
fast = fast.next.next;
slow = slow.next;
}

while (head != slow.next) {