@rkenmi - Detecting a cycle in a linked list

# Detecting a cycle in a linked list

## Problem

Detect a cycle in a linked list and return the node that represents the start of 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
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):
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

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