3056. 链表查询

这道题给的程序是有错的，要把所有的\\n改成\n

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

这数据真是绝了，怎么写样例都能过
首先别理解错了，是倒数第n个，其次，要考虑n太大，不存在的情况

// * 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
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

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()
{ 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;ivalue=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;
}

首先, 这个题的\n都错了, 记得改掉.

其次, malloc.h是个非标准的, 跟linux绑定很深的库, 如果过不了请换成cstdlib(c++)或stdlib.h(c)

最后, 给的程序里的那个t其实就是链表的总长度(没什么意义).

话说回来没想到我也要做……

利用的思想是环形数组。开一个 $n$ 个大小的数组，然后循环就好啦。

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

这道题出得像屎一样，我心疼那些学长们。