考研真题

已知一个带有表头节点的单链表，结点结构为data|next
假设该链表只给出了头指针head。在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第K个位置上的节点，K为正整数。若查找成功，输出该节点的data值，并且返回1，否则，只返回0.
要求：
- 描述算法基本设计思想
- 描述算法详细实现步骤
- 用CC++java语言实现代码，关键之处请给出简要注释

#include<stdio.h>
#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode;




///关键的算法部分开始
int findNode(LNode *head,int k)
{
    LNode *q,*finds;
    q=head->next;
    finds=head;
    int i=1;
    while(q!=NULL)
    {
        q=q->next;
        ++i;
        if(i>k)
        {
            finds=finds->next;
        }
    }
    if(finds == head)//如果链表没有k个节点，直接返回
        return 0;
    else
    {
        cout<<finds->data;
        return 1;
    }
}
//关键部分结束



void saveListnext(LNode *&L,int x[],int n)//尾插
{
    L = (LNode *)malloc (sizeof(LNode));
    L->next=NULL;

    LNode *q;
    q=L;
    LNode *s;
    for(int i=0;i<n;i++)
    {
        s=(LNode *)malloc(sizeof(LNode));
        s->data = x[i];

        q->next=s;
        q=q->next;
    }
    q->next=NULL;
}
void printList(LNode *L)
{
    LNode *q;
    q=L->next;
    int i=0;
    while(q!=NULL)
    {
        if(i++)
            putchar(' ');
        printf("%d",q->data);
        q=q->next;
    }
    printf("n");
}
int main(void)
{
    LNode *L;
    int x[8]={4,5,6,7,8,9,10,11};
    saveListnext(L,x,8);
    printList(L);
    findNode(L,3);
}