# Grokking the Coding Interview's Fast and Slow Pointers

Linked list cycle, Start of a linked list cycle, Happy number, Middle of a linked list, Palindrome linked list, Reorder a linked list

### 1. Given the head of a singly linked list, write a function to determine if it contains a cycle.

Approach:

```
- Have a slow pointer move one step at a time while the fast one move
2 steps at a time.
- If the linked list has a cycle, the fast pointer will catch the slow one.
```

Cost:

```
- O(n) time, O(1) space.
```

### 2. Given the head of a singly linked list, write a function to find the starting node of the cycle.

Approach:

```
- Similar to finding a cycle in a linked list problem, can also determine
the start of its cycle and calculate length k of the cycle.
- Have one pointer at the beginning and one at kth node of the linked list.
- Move both of them until they meet at the start.of the cycle.
```

Cost:

```
- O(n) time and O(1) space.
```

### 3. Write an algorithm to determine if a number is happy.

Any number will be called a happy number if, after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to 1.

Example:

```
- Input: 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
```

Approach:

```
- Since the process always end in a cycle, we can use a similar approach to
finding a cycle in linked list problem.
- Once is cycle is found, check if it is stuck on 1.
```

Cost:

```
- O(n) time, O(1) space.
```

### 4. Given the head of a singly linked list, write a function to return the middle value.

Approach:

```
- Have a slow pointer move one step at a time while the fast one move
2 steps at a time.
- Once the fast one reaches the end, the slow is in the middle.
```

Cost:

```
- O(n) time, O(1) space.
```

### 5. Given the head of a singly linked list, write a function to determine if it is a palindrome in constant space.

Approach:

```
- Find the middle of the linked list and reverse a half list
- After comparing the first half with the reversed half to check if it's
a palindrome, revert to the half to original form.
```

Cost:

```
- O(n) time, O(1) space.
```

### 6. Given the head of a singly linked list, write a function to reorder it such that nodes from the second half are inserted alternately to the nodes from the first half in reverse order.

Approach:

```
- Similar to palindrome linked list problem, can also use a trick to
reverse the second half and rearrange them in the required order
using fast and slow pointers.
```

Cost:

```
- O(n) time, O(1) space.
```

For more coding problems, please visit https://github.com/hoanhan101/algo.

Tagged: #grokking-the-coding-interview, #algorithm