Coding Patterns: Fast & Slow Pointers
In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.
Previous posts were about Sliding Window and Two Pointers patterns and today, we will introduce Fast & Slow Pointers pattern (a.k.a. Floyd’s Tortoise and Hare Algorithm) which is very useful when dealing with cyclic Linked Lists or Arrays.
By moving at different speeds, the algorithm proves that the two pointers are going to meet eventually. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.
Problem: Linked List Cycle
LeetCode 141 - Linked List Cycle [easy]
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3, 2, 0, -4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to
the second node.
Example 2:
Input: head = [1, 2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to
the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
Fast & Slow Pointers Solution
If you need to refresh your knowledge in Linked Lists, I would suggest to do so before jumping into the solution.
Imagine two racers running in a circular racing track. If one racer is faster than the other, the faster racer is bound to catch up and cross the slower racer from behind. In each iteration, Tortoise 
(slow pointer) moves one step and the Hare 
(fast pointer) moves two steps.
- If the Linked Lists does not have a cycle in it, Hare will reach the end of the Linked Lists before the Tortoise and this will reveal that there is no cycle in the Linked Lists.
- The Tortoise will never be catch up the Hare if there is no cycle in the Linked Lists.
If at any stage the Tortoise (slow pointer) meet with the Hare (fast pointer), we can conclude that the Linked Lists is cyclic. Here is the proof:
- If the Hare (fast pointer) is one step behind the Tortoise (slow pointer): The fast pointer moves two steps and the slow pointer moves one step, and they both meet.
- If the Hare (fast pointer) is two steps behind the Tortoise (slow pointer): The fast pointer moves two steps and the slow pointer moves one step. After the moves, the fast pointer will be one step behind the slow pointer, which reduces this scenario to the first scenario. This means that the two pointers will meet in the next iteration.
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow, fast = head, head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True # found the cycle
return False
Time Complexity: O(N) where N is the number of nodes in the Linked Lists.
Space Complexity: O(1), algorithm runs in constant space.
Problem: Linked List Cycle II
LeetCode 142 - Linked List Cycle II [medium]
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3, 2, 0, -4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to
the second node.
Example 2:
Input: head = [1, 2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to
the first node.
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it without using extra space?
Fast & Slow Pointers Solution
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow, fast = head, head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:
current = head
while current is not slow:
current = current.next
slow = slow.next
return slow
return None
Time Complexity: O(N) where N is the number of nodes in the Linked Lists.
Space Complexity: O(1), algorithm runs in constant space.
As you can see, only difference between two problems is the part:
if slow == fast:
current = head
while current is not slow:
current = current.next
slow = slow.next
return slow
Let’s try to understand it with a diagram:
When the Hare (fast pointer) and the Tortoise (slow pointer) meet at point -4, the length they have run are A+2B+C (for Hare) and A+B (for Tortoise).
Since the fast pointer is 2 times faster than the slow pointer, A+2B+C == 2(A+B), then we get A==C.
So, when another pointer (current) run from head to 2 (distance A), at the same time, previous slow pointer will run from -4 to 2 (distance C), so they meet at the pointer 2 together, which is the point where cycle begins as problem asked.
How to identify?
This approach is quite useful when dealing with cyclic Linked Lists or Arrays.
When the problem involves something related to cyclic data structures, you should think about Fast & Slow Pointers pattern.