Find nth element from last in a Linked List

One very interesting problem is to find the nth element from the end in a linked list. Now it's very easy to find the nth element from the beginning of the list and can be done in one traverse. So what are the various solutions we can think of.

One of the methods involves traversing the list once to find the length say the length is l.

Now we need to find the nth element from last that means (l-m)th element from head so we need to traverse the list once again until we reach (l-m)th element.

This method is good for small lists where the number of elements to be traversed are not large but if the number is large then there would be a problem since there would be twice the traversal.

Another method is to hold a pointer to a node which is m nodes ahead and traverse the list until the node reaches last so the node which is m nodes behind is the desired node.

Lets define a simple Node class :



The code for this algorithm is below:



There is a one more solution in which we don't have to as much traversing as we had done above. This is a bit complicated but interesting. In it we traverse the list in rounds of n nodes and maintain a pointer to the node which is beginning of the node which is m nodes behind the beginning of current node. e.g. if a list has 10 elements and the elements are 1-2-3-4-5-6-7-8-9-10 and we need to find the 4th element from last i.e. 7 we would proceed the list in a set of 4 elements so that when current reaches 5th node, pointer is at 1st node. When it reaches 9th node, the pointer is at 5th node. After 9th node we get to the last node in 2 turns so mth node will be 5+2 i.e. 7th node. The code to implement this is as follows :