## mth from the last element of a singly linked list

Write a program to find the mth from the last element of a singly linked list So for the linked list shown m= 0 would return the node with information field 1203 (tail element) and m = 1 would return node with information field 1202.

Solution:

This is a very common interview question. Let’s look at a very simple solution.

1. Traverse the list and count the number of nodes.
2. Calculate the offset of the mth from last element from the start using  offset = (length – m)
3. Traverse the linked list again (for int i=1 ; i <=offset; i++) and return the current node.

However there must be a better way of approaching this instead of using loops to traverse the list twice.

Another solution can be as follows:

1. Initialize two pointers p and q both pointing to the head of the linked list.
2. Now let’s make the distance between p and q equals to m by incrementing the q pointed m times.
3. Now check if q-> next == NULL (means we have reached the end of the linked list and p is at m positions from the last element so we return node pointed by p) else increment both points p = p-> next and q = q-> next and repeat step 3 again.

Rough implementation in C++ would be as follows:

Node * mthfromLast(Node * head, int m){

{   return NULL;
}

Node * p, *q = head;

for (int i = 0 ; i < m; i++){
if(q->next == NULL)

{ return NULL;
}

q = q-> next;
}
while(q->next!= NULL) {

p = p-> next;

q = q-> next;

}
return p;
}