Linked Lists: Finding Nth Node From End of List

Last week, I wrote about how to use a slow and fast point to find the middle node of a linked list. We can use the same approach to find N nodes from end.

For example, we have a linked list with nodes 1,2,3,4,5 and N =2. We would return the node with a value of 4 since it is 2 nodes away from the end.

Setting up pointers

We will again start both pointers on the head. Instead of moving FAST move twice as fast. We will move fast one node at a time. However, we want to give FAST a head start. We will move FAST, N times before SLOW starts. Since N is 2, we will move FAST up two nodes.

Now we can move both pointers until FAST is NULL.

We can just return SLOW!

You can see that FAST and SLOW pointers work for a wide range of different problems.