単一チェーンテーブルの最後からn番目のノードを検索

http://www.nowamagic.net/librarys/veda/detail/496
単一チェーンテーブルの最下位からn番目のノードを1回の遍歴で見つけると、チェーンテーブルはかなり大きくなり、補助空間を使用することができますが、補助空間の数は固定されなければなりません.nとは関係ありません.
片方向チェーンテーブルは,末尾まで遍歴した後にN個のノードを逆数できないことが特徴である.したがって,末尾に到達しながら最後からN番目のノードを見つけなければならない.
順数n個でも逆数n個でも,実は距離−スケール問題である.スケールは、セグメントの2つの端点で測定できる距離であり、next=NULLのため、最後から最初のノードを判断することができます.2つのポインタを使用して距離を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歩歩く.では、一つが行き止まりになると、もう一つは真ん中に行きます.単一の一方向チェーンテーブルを巡回して中間ノードを見つける
view source
print ?

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

#include <iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

struct  node
{
    int date;
    node *next;
};

node *createLinkList()
{
     node *head,*p;
     int x;
     head = (node *)malloc(sizeof(node));
     head->next = NULL;
     scanf("%d",&x);
     while(x!=0)
     {
         p = (node *)malloc(sizeof(node));
         p->date = x;
         p->next = head->next;
         head->next = p;
         scanf("%d",&x);
     }
     return head;
}

void printLinkList(node *head)
{
    node *p = head->next;
    while(p!=NULL)
    {
        printf("%d  ",p->date);
        p = p->next;
    }
}

node *getLastNode(node *head,int n)
{
    node *first = head;
    node *second = head;
    int counter = 0;
    for(;counter<n;counter++)
    {
        if(first==NULL)
        {
            printf("      ");
            //        return;
            return NULL;
        }
        first = first->next;
    }

    while(first!=NULL)
    {
        first = first->next;
        second = second->next;
    }
    return second;
}

node *getMiddleNode(node *head)
{
    node *p1 = head->next;
    node *p2 = head->next;
    while(p1)
    {
        p1 = p1->next;
        if(p1)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    return p2;

}

int main()
{
    node *head = createLinkList();
    printLinkList(head);
    int num;
    scanf("%d",&num);
    node *result = getLastNode(head,num);
    printf("%d
",result->date);
    node *middle = getMiddleNode(head);
    printf("%d
",middle->date);
    return 0;
}