# Linked List Cycle II

## More work after Linked List Cycle I

To find where the cycle begins, we can use a fast-slow pointer.

The faster one walks `length of the cycle`

steps before the slower one, and then, the slower one start to walk.
Where the faster one and slower one meet is the point that the cycle begins.

## Measure the length of the cycle

After the fast-slow runners encounter, let them go on running until they will meet at some point.

If slow-runner walks `1`

step each loop, when they meet again, the slow-runner will walk `length of the cycle`

steps.

So, code might be like

```
loop until fast meets slow
if not meet first time
length = length + 1
```

### Source code *Read on Github*

```
1 /**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode(int x) {
7 * val = x;
8 * next = null;
9 * }
10 * }
11 */
12 public class Solution {
13 public ListNode detectCycle(ListNode head) {
14 // IMPORTANT: Please reset any member data you declared, as
15 // the same Solution instance will be reused for each test case.
16
17 if(head == null) return null;
18
19 ListNode fast = head;
20 ListNode slow = head;
21
22 boolean meet = false;
23
24 int lenc = 0;
25
26 while ( slow.next != null){
27
28 slow = slow.next;
29
30 if(slow == null) return null;
31
32 if(fast.next == null) return null;
33
34 fast = fast.next.next;
35
36 if(fast == null) return null;
37
38 if(slow == fast) {
39
40 if(meet) break;
41
42 meet = true;
43 }
44
45 if(meet){
46 lenc++;
47 }
48 }
49
50 if(meet){
51
52 slow = head;
53 fast = head;
54 for(int i = 0; i< lenc; i++){
55 fast = fast.next;
56 }
57
58 while(slow != fast){
59 slow = slow.next;
60 fast = fast.next;
61 }
62
63
64 return slow;
65
66 }
67
68 return null;
69 }
70 }
```