##### Updated on February 10, 2019

## Problem

Detect a cycle in a linked list and return the node that represents the

startof the cycle.

## Input

`head`

: a pointer to the linked list

## Approach

First, lets concentrate on how to detect a cycle in a linked list.

There are numerous ways to brute force this, but the most **efficient** approach is to use two pointers - a *slow* pointer and a *fast* pointer.

The *slow* pointer moves forward **one** node at a time, and

the *fast* pointer moves forward **two** nodes at a time.

If a cycle was to exist, then our pointers will eventually see the same nodes over and over again. By having a pointer that moves one additional step forward at each iteration, we will eventually reach a point where the *slow* pointer points to the same node as the *fast* pointer.

Consider the following linked list sequence:

`A -> B -> C -> A -> B -> C -> A -> B -> C ...`

If we let *slow* start at `A`

and *fast* start at `A`

, they will traverse through the nodes in this fashion:

# of iterations | slow (pointer) | fast (pointer) |
---|---|---|

0 | A (head) | A (head) |

1 | B | C |

2 | C | B |

3 | A | A |

As you can see, after 3 iterations, both pointers will point to the same node.

## Solution

```
def rotate_2d_array(A):
for j in range(0, len(A) // 2):
for i in range(j, len(A) - 1 - j):
old = A[j][i]
A[i][~j], old = old, A[i][~j]
A[~j][~i], old = old, A[~j][~i]
A[~i][j], old = old, A[~i][j]
A[j][i] = old
return A
```

```
# Note that this function returns a boolean
def has_cycle(head):
slow = fast = head
while slow and slow.next and fast and fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
if slow == fast:
return True
return False
```

### Returning the beginning of a cycle

When `slow == fast`

, it might be believed that these two variables point to the node that represents the beginning of a cycle. However, this isn't the case.

Consider the following linked list sequence:

`Z -> A -> B -> A -> B -> A -> B ...`

If we let *slow* start at `Z`

and *fast* start at `Z`

, they will traverse through the nodes in this fashion:

# of iterations | slow (pointer) | fast (pointer) |
---|---|---|

0 | Z (head) | Z (head) |

1 | A | B |

2 | B | B |

Here, we have a match where *slow* and *fast* both points to node **B**.

`Z -> A -> B -> A -> B -> A -> B ...`

But looking at the actual sequence, we see that the cycle starts at node **A**.

### Where is the beginning of a cycle?

The beginning of a cycle can be found by counting the length of the cycle. This can be done by taking a copy of the matched node above (`slow`

or `fast`

) and counting how many iterations it takes to get to the same matched node.

```
temp = slow
count = 0
while temp:
temp = temp.next
count += 1
if temp == slow:
break
```

Once we have the count of the cycle, we'll grab a fresh pointer to `head`

called `loop_start`

and move it forward by `count`

times.

```
loop_start = head
for _ in range(count):
loop_start = loop_start.next
```

Then we grab another fresh pointer to `head`

called `start`

, and iterate both of these pointers simultaneously (moving forward one node at a time) until we have a match.

```
start = head
while loop_start != start:
loop_start = loop_start.next
start = start.next
return loop_start
```

The while loop above may look scary, but at this point we have already confirmed that a linked list cycle exists.

Putting everything together, we have:

```
def has_cycle(head):
slow = fast = head
while slow and slow.next and fast and fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
if slow == fast:
temp = slow
count = 0
while temp:
temp = temp.next
count += 1
if temp == slow:
break
loop_start = head
for _ in range(count):
loop_start = loop_start.next
start = head
while loop_start != start:
loop_start = loop_start.next
start = start.next
return loop_start
```

References: Floyd