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;

}