Posted on 2006-06-23 17:37
Enjoy Life 阅读(1028)
评论(0) 编辑 收藏 引用 所属分类:
程序员面试功略
用单链表实现查找（获取）倒数第m个元素，当m=0时就是指单链表最后一个元素。
最佳算法之一：
用两个指针，一个指向当前遍历的元素，CurPos，另外一个指向CurPos前第m个元素，
然后两个指针同时一直向单链表后序元素遍历，直到CurPos指向最后一个元素为止。
element *FindMToLast(element *head, int m){
int i;
element *CurPos, *MToCurPos;
CurPos = head;
for(i=0; i<m; i++){
if(CurPos->next){
CurPos = CurPos->next;
}else{
/*
不到M个元素*/
return NULL;
}
}
/*Start mbehind at beginning and advanced pointers
*together until current hits last element
*/
MToCurPos = head;
while(current->next){
current = current->next;
MToCurPos = MToCurPos->next;
}
/*
*MToCurPos now points to the element we were
*searching for, so return it
*/
return MToCurPos;
}