What is the fast and slow pointer pattern, and which problems does it solve?
The fast and slow pointer pattern is the technique of using two pointers that move through the same structure at different speeds, so that one of them reaches the end while the other is exactly half way through.
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def middle_node(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow
So which problems does it solve? Here are the main ones.
the problem what the two pointers do
--------------------------- ------------------------------------
find the middle node fast runs off the end, slow is half way
detect a cycle fast catches up with slow
find the cycle entry after they meet, walk one node each
remove the nth from the end they start n apart and move together
check if a list is a palindrome one goes forward, one goes back
find the intersection they meet at the first shared node
And the pattern works in any structure where you can move forwards one step at a time, and where the end is marked by nothing. A linked list is the usual case. An array works as well, if you use the end of the array as the end marker.
And why is the pattern useful? Three reasons.
The first one is that it does not need to know the length in advance. The counting version has to walk the list once to find the length and then walk it again. The two pointer version needs one walk.
The second one is that it uses O of 1 for the space. There is no list of the nodes that you have seen and no table of answers.
The third one is that the two pointers often end up in a useful place at the same time. The cycle detection is the clearest example. The slow pointer catches up with the fast one exactly when they are both inside the cycle, and that fact is what makes the whole thing work.
And there is one rule to remember about the loop condition. When the fast pointer moves two steps at a time then the loop has to check that there are two nodes left, and not just one. So the condition is fast is not None and fast.next is not None. Get that wrong and the slow pointer ends up one place too far on an even length list.
So the rule to remember is this. Two pointers, two speeds, and the fast one checks two steps ahead.
The last question in this topic shows the cycle entry problem.