**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.

- Traverse the list and count the number of nodes.
- Calculate the offset of the mth from last element from the start using offset = (length – m)
- 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:

- Initialize two pointers p and q both pointing to the head of the linked list.
- Now let’s make the distance between p and q equals to m by incrementing the q pointed m times.
- 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){

if(head==NULL|| m < 0)

{ 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;

}

Singly Linked List Image was taken from : http://www.tech-faq.com/images/singly-linked-list_clip_image002.jpg

### Like this:

Like Loading...

*Related*

## Leave a Reply