Given a linked list, how do efficiently find the nth node from the end?
For example in the following linked list, 3rd node from the end is ‘6’.
2 -> 1 -> 6 -> 5 -> 9
One obvious method is to find the length of the linked list (len) by going through the list. calculate the difference (len – n). Again traverse the list (len – n) times to get the required node. Though this approach is O(n), we traverse the list twice.
We can do it in just one iteration itself. We take two pointers one main pointer (ptr) and one helper pointer (hPtr). First we travel a distance of n nodes with hPtr. Then we start from the beginning with main pointer also. By the time the hPtr reaches the end, ptr would be pointing to the nth node from the end.
Here is Object Oriented implementation of this in C++