# linked list cycle I and II

## linked list cycle I and II

These two question I have never met before, and looks interesting.

A fast pointer and a slow pointer,each time the fast one walk two steps and the slow one walk one step. If there is a cycle and the the fast one will meet the slow one one.

`````` 1 /**
2  * Definition for singly-linked list.
3  * struct ListNode {
4  *     int val;
5  *     ListNode *next;
6  *     ListNode(int x) : val(x), next(NULL) {}
7  * };
8  */
9 class Solution {
10 public:
12         if ( !head ) {
13             return false;
14         }
17         while ( fast->next && fast->next->next ) {
18             slow = slow->next;
19             fast = fast->next->next;
20             if ( fast == slow ) {
21                 return true;
22             }
23         }
24         return false;
25     }
26 };``````

This seems a little harder than Linked list cycleI. Assuming that, the lenth of the cycle is `len`, and when the two pointer meet, the slow one walked `m` steps, and there are `b` steps between the enterance of the cycle and the point where they meet.

1. When the two pointer meet, the slow one walked `m` steps, and the fast one walked `2m` steps.
2. So ` 2m - m = k*len ` means the fast one walked serveral cycles.
3. The entrance to of the cycle is at `m-b`
4. Now ,apparently, the head to the enterance and the meet point to the enterance are both `m-b`.
5. Make the slow pointer back to the head, the fast pointer stay at where they meet. This time, both of them walk one step each iteration. Finally they will meet in the enterance.
`````` 1 /**
2  * Definition for singly-linked list.
3  * struct ListNode {
4  *     int val;
5  *     ListNode *next;
6  *     ListNode(int x) : val(x), next(NULL) {}
7  * };
8  */
9 class Solution {
10 public:
12         if ( !head ) {
14         }
17         int mark = 0;
18         while ( fast->next && fast->next->next ) {
19             slow = slow->next;
20             fast = fast->next->next;
21             if ( fast == slow ) {
22                 mark = 1;
23                 break;
24             }
25         }
26         if ( 0 == mark ) {
27             return NULL;
28         }