# Linked List Cycle

## Fast slow pointer

A linked list with cycle.

```
1----->-----2----->-------3
| |
| |
^ V
| |
| |
5------<------4
```

let two people run in it, one take 1 step each time, the other take 2 steps each time. They will meet at a point after some time running.

imagine month and week, the first day of month and the first day of week will meet sometimes.

So, let a fast runner and a slow runner run in the linked list

- they will collide if the linked list has a cycle.
- the faster one will find the exit if there is no cycle.

### 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 boolean hasCycle(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 if(head == null) return false;
17
18 ListNode fast = head;
19 ListNode slow = head;
20
21
22 while(slow.next != null){
23
24 if(fast.next == null) return false;
25
26 fast = fast.next.next;
27
28 if(fast == null) return false;
29
30 slow = slow.next;
31
32 if(fast == slow) return true;
33 }
34
35 return false;
36 }
37 }
```