程序设计能力实训

1255. 链表查询

单点时限: 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: 等),然后在一行中输出相关数据(数据的意义不在这里描述)。

样例

Input
3
1100 2 5 2
1 2 3 4
4 3 2 1
Output
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;
}
不限期开放

题目列表