题目：
分析：09年的链表题目比较简单，直接构建链表，然后根据不同思路模拟即可。
思路一：循环遍历
思考：最容易想到的思路，直接暴力循环。偷了一下懒，变量名称没用题目的，考试写的时候不能错。写了完整的运行代码，考试的时候看题目要求写上链表定义，实现函数即可。
#include <iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node* next;
//数据域整型，指向空
}node,*list;//单个节点，链表指针
int create(list &L)
{
int n;
node*t,*r;//临时指针和尾指针
r=L;
cin>>n;
for(int i=0;i<n;i++)
{
t=new node;
cin>>(t->data);
t->next=NULL;
r->next=t;
r=t;
}
}
void print(list L)
{
node*t;
t=L->next;
while(t!=NULL)
{
cout<<t->data<<' ';
t=t->next;
}
}
int check(list L)
{
int k;
cin>>k;
int cnt=0;
node* t;
t=L->next;
while(t!=NULL)
{
cnt++;
t=t->next;
}
if(k>cnt) return 0;
t=L->next;
int cout=0;
while(t!=NULL)
{
if(cout==cnt-k) return t->data;
cout++;
t=t->next;
}
}
int main()
{
list L;//单链表/头指针
L=new node;//创建单链表
L->next=NULL;
create(L);//插入值
cout<<check(L);
//print(L);
return 0;
}时间复杂度：O（n），空间复杂度O（1）。两次循环遍历，n为链表长度。没有开多余的空间，题目表明的是处理一条现成的链表。
思路二：找技巧
思考：定义两个指针，当指针1移动到K个时，指针2才开始移动。当指针1到达最后时，指针2到达的地方就是倒数第k个地方。前提是存在倒数第k个地方。
。
#include <iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node* next;
//数据域整型，指向空
}node,*list;//单个节点，链表指针
int create(list &L)
{
int n;
node*t,*r;//临时指针和尾指针
r=L;
cin>>n;
for(int i=0;i<n;i++)
{
t=new node;
cin>>(t->data);
t->next=NULL;
r->next=t;
r=t;
}
}
void print(list L)
{
node*t;
t=L->next;
while(t!=NULL)
{
cout<<t->data<<' ';
t=t->next;
}
}
int check2(list L)
{
int k,cnt=1;
cin>>k;
node*p,*q;
p=L->next;
q=L->next;
while(q->next!=NULL)
{
if(cnt<k)
{
q=q->next;
}
else
{
q=q->next;
p=p->next;
}
cnt++;
}
if(cnt<k) return 0;
return p->data;
}
int main()
{
list L;//单链表/头指针
L=new node;//创建单链表
L->next=NULL;
create(L);//插入值
cout<<check2(L);
//print(L);
return 0;
}
