Linked Lists: Slow and Fast
95% of all singly linked list problems are solved with some type of pointers. In this example, we are going to use two pointers to find the mid point of a linked list.
A linked list is a data structure where a node (an object with a “value” and a “next” attribute that points to the next node).
Pointers
We will use two pointers. A pointer is just a variable that references a node. A pointer named “slow” will move at 1x speed and a pointer named “fast” will move at 2x speed. We will keep moving the pointer until the fast pointer moves to the very end.
We start both pointers on the very first node which is the head\
Starting:
We will keep moving the pointers until the fast node hits null.
First loop:
Second loop:
We can stop at this point because out fast.next is equal to null. We can not advance the fast pointer anymore. Our slow pointer is sitting on the exact middle point.
We can just return the slow pointer as the answer. Voila!
