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
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