Tuesday, November 07, 2006

Find the nth element from the back of a singly linked list

This is most ever question asked by many top companies.

The question goes as follows :
How would you find the nth element from the back of a singly linked list?

And the following might be a solution:
1) have two ptrs. F_Ptr & S_Ptr.
2) Let the ptrs point to the START.
3) Take n as the offset.
4) Start traversing the S_Ptr after the F_Ptr after n.

Suppose u want to find 5th element from the last of the list, then
1) n = 5 // 5th element from the last

2) check atleast this many elements are there in the list before begining

// traverse the F_Ptr offsetfor(;n!=0;n--,F_Ptr->next);
// now set the S_Ptr to trail the F_Ptr
S_Ptr = F_Ptr;
for(;F_Ptr!=NULL; S_Ptr=F_Ptr; F_Ptr=F_Ptr->next)

Now when F_Ptr = Null, S_Ptr is just trailing behind right! it will be pointing to the n'th element from the last.

When F_Ptr reaches end (i.e., F_Ptr is NULL)S_Ptr points to the 5th element from the last.

No comments: