## Find the nth node from the end in a linked list.

Today we have a very easy one in our hands. The problem statement asks you to find the nth from last node. How do you plan to do this?

Some of my friends said, “We’ll move through the whole linked list once, and calculate its length. Then we’ll start over and go to length-nth node”. Well, yeah. You can certainly do that and the time complexity will be O(n). However you are traversing the whole linked list *twice* which is not advisable. You can instead finish this task in one traversal of the linked list.

Can you make a guess? Well, here’s how it will be done:

Take 2 pointers both pointing at START. Now move the second pointer forward to the nth node (from start). Next, you start moving both these pointers forward by 1 node at a time. So we are maintaining a separation of n nodes between our two pointers. As soon as your second pointer reaches the end of the linked list, you can say that the first pointer is currently at the nth node from the end.

Sly, eh?! Have fun with this new algorithm! 🙂

I really like the 2 pointer approach. But there is a recursive solution to this as well as written here – http://k2code.blogspot.in/2010/04/return-nth-node-from-end-of-linked-list.html:

Thanks.

While I haven’t gone over the correctness of the code you wrote, I agree that a recursive method is possible and suggested in multiple places on the internet. I would strongly discourage using recursion whenever it can be avoided, since recursion pushes each function execution state onto the stack which is highly memory intensive.