# 3056. 链表查询

NODE *FindLastNthNode(NODE *h, int n){
NODE * ptr = h;
int sum = 1;
while (ptr->next != 0)
{
ptr = ptr->next;
sum++;
}
int move = sum - n;
ptr = h;
if(move < 0) return 0;
for (int i = 0; i < move; i++)
ptr = ptr->next;
return ptr;
}

// * 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
/
NODE* k=h;
int totstep=0;
while(k->next!=0) {k=k->next;totstep++;}

if(n>totstep+1) return 0;
for(int i=1;i<=totstep-n+1;i++)
if(h->next==0) return 0;
else h=h->next;
return h;
}
///////////////////////////////////////////////////////

/*********/
/ /
/ DON’T MODIFY following code anyway! /
/ /
/*********/

### include

static unsigned long next = 1;
int RND()
{ next = next * 1103515245 + 12345;
return (unsigned) (next/65536) % 32768;
}
void SETSEED(unsigned seed) { next = seed; }
void solve()
scanf(“%d%d%d%d”,&s,&t,&m,&n); SETSEED(s);
for (i=0;ivalue=RND()%m; p->next=0;
}
else printf(“NONE:”);
n=0;
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;
}

NODE *FindLastNthNode(NODE *h, int n) {
NODE **arr = (NODE **)malloc(sizeof(NODE *) * n);
memset(arr, 0, sizeof(NODE *) * n);
size_t pos = 0;
for (NODE *iter = h; iter != NULL; iter = iter->next) {
arr[pos] = iter;
if (++pos == n) {
pos = 0;
}
}
NODE *ret = arr[pos];
free(arr);
return ret;
}