C/C++面试之算法系列－－一次遍历找链表倒数第n个节点

转自：http://blog.csdn.net/sailor_8318/article/details/3397116

?

思科和横河电机面试题。通过一次遍历找到单链表中倒数第n个节点，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。

?

单向链表的特点是遍历到末尾后不能反向重数N个节点。因此必须在到达尾部的同时找到倒数第N个节点。

?

不管是顺数n个还是倒数n个，其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量，我们能够判断倒数第一个节点，因为他的next==NULL。如果我们用两个指针，并保持他们的距离为n，那么当这个线段的右端指向末尾节点时，左端节点就指向倒数第n个节点。

?

iNode * GetLastNnode(iNode * head, int n)

{

????????iNode * pfirst=head;

????????iNode *psecond=head;

???????

????????int counter;

????//第1步：建立标尺，移动pfirst N步

????????for(counter=0; counter<n; counter++) {

????????????????if((NULL == pfirst)

???????????????????????break; //?此时pfirst->next无意义

????????????????pfirst=pfirst->next;

????????}

???????

????????if(n != counter) //长度不够n，未找到倒数第n个节点

????????????????return NULL;

?

????????//第2步：保持距离让标尺向右移动，直到右端指向末尾，左端即结果

????????while(pfirst!=NULL) {

????????????????pfirst=pfirst->next;

????????????????psecond=psecond->next;

????????}

????????return psecond;

}

?

?

iNode * GetLastNnode ( iNode *head, int n)

{

????iNode * pfirst = head;

????iNode *?psecond = NULL;//可能没有n个

????while( n-- > 0 && (pfirst!= NULL)

????{

????????pfirst = pfirst ->next;

????????}

?

????if(pfirst!=?NULL)//?有n个节点

????????psecond = head;

?

????while(pfirst!=NULL)

????{

?????????pfirst = pfirst ->next;

?????????psecond = psecond ->next;

????}

????return psecond;?//只有一个出口，无论是否有n个节点，都能返回正确值

}

?

一次遍历单向链表找到中间节点

?

和上面的思路类似，设置2个指针，一个走2步时，另一个走1步。那么一个走到头时，另一个走到中间。

iNode *?GetMiddleNode ( iNode *head)

{

????iNode *p1 = head;

????iNode *p2 = p1;

????while( p2 )

????{

????????p2 = p2->next;

????????if(p2)

????????{

????????????p2 = p2->next;

????????????p1=p1->next;

????????}

????}

????return p1;

}