Fast and Slow Pointer Design Pattern

Fast and Slow Pointer Design Pattern

The fast and slow pointer design pattern is another popular design pattern that is used for solving problems related to cyclic linked lists or to determine if there is an indefinite loop. The design pattern is also popularly called as hare and tortoise design pattern.

In fast and slow pointer design patterns, we will have two pointers. The first pointer moves at a normal speed but another pointer moves double the speed of the first pointer.  If there is no cycle in the list then these two pointers will never meet each other but if there is a cycle in the list then these pointers will eventually meet with one another at a point.

Let's try to understand with some illustrations how the design pattern works.

If we look at the two scenarios on the image. The first image illustrates the situation when there is no loop. During that case, our fast pointer will reach the end of the line and we can end the loop.

In the second scenario, our fast pointer and the second pointer will meet up at one point and they will point at the same location, unlike the first scenario. Once we know, at one point these two pointers will be pointing at the same location, we can conclude that there is a loop in the line.