单点时限: 7.0 sec
内存限制: 256 MB
给定一个存储了若干个整数的单向链表和一个整数 n(值范围为 [1,105])，查找单向链表中倒数第 n 个节点（尾节点为倒数第 1 个节点）。
结构体类型 NODE 表示一个单向链表的节点定义。
// * Definition of the structure *
typedef struct Node
{ int value;
struct Node *next;
} NODE;
定义函数 FindLastNthNode, 返回指向倒数第 n 个节点的指针，若不存在，则返回 0：
//** Specification of FindLastNthNode ****
NODE FindLastNthNode(NODE h,int n);
/* PreCondition:
h is a head pointer of a linked-list, n is an integer
PostCondition:
return the pointer of the last nth node in the linked-list,
or 0 if such node can’t be found
*/
第 1 行：整数 $T$ ($1 \le T \le 10$) 为问题数。
第 2∽T+1 行：每一个问题一行数据（数据的意义不在这里描述）。
对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等），然后在一行中输出相关数据（数据的意义不在这里描述）。
3 1100 2 5 2 1 2 3 4 4 3 2 1
case #0: 2:2 2 case #1: NONE:2 1 case #2: 1:1 0 1
程序：
// ********** Specification of struct Node **********
typedef struct Node
{ int value;
struct Node *next;
}NODE;
/*/////////////////////////////////////////////////////*/
NODE *FindLastNthNode(NODE *h,int n)
/* PreCondition:
h is a head pointer of a linked-list, n is an integer
PostCondition:
return the pointer of the last nth node in the linked-list,
or 0 if such node can’t be found
*/
{ //TODO: your definition
}
/*/////////////////////////////////////////////////////*/
/***************************************************************/
/* */
/* DON'T MODIFY following code anyway! */
/* */
/***************************************************************/
#include <stdio.h>
#include <malloc.h>
static unsigned long next = 1;
int RND()
{ next = next * 1103515245 + 12345;
return (unsigned) (next/65536) % 32768;
}
void SETSEED(unsigned seed) { next = seed; }
void solve()
{ int i,s,n,m,t; NODE* head=0,*p,*tail;
scanf("%d%d%d%d",&s,&t,&m,&n); SETSEED(s);
for (i=0;i<t;i++)
{ p=(NODE*)malloc(sizeof(NODE));
p->value=RND()%m; p->next=0;
if (head==0) head=p; else tail->next=p; tail=p;
}
if (p=FindLastNthNode(head,n)) printf("%d:",p->value);
else printf("NONE:");
n=0;
while (head)
{ p=head; head=head->next;
if (t<100||t>100 && n<100)
{ printf("%d",p->value); if (head) printf(" ");}
n++; free(p);
}
printf("\\n");
}
int main()
{ int i,t; scanf("%d\\n",&t);
for (i=0;i<t;i++) { printf("case #%d:\\n",i); solve(); }
return 0;
}