一.2009年
注意事项：1.结构体是data和link 2.不能改变链表 3.要返回0或1
1.暴力解法：10分
分析:要查找倒数第k个结点，但是单链表没有这个功能，只有双链表有，所以把倒数转换成正数。
找关系：总长—k+1=正数位置 // m=L-k+1;
遍历了2次：时间复杂度：0（n） 空间复杂度：0（1）
//求总长,因为后面要用到总长度计算
int len(LNode *L){
LNode *p=L->link;
int n=0;
while(p){
p=p->link;
++n;
}
return n;
}
//查找
int find(LNode *L,int k){
int m=len(L)-k+1; //正数位置
int i=0;
if(m<=0) return 0;
while(ilink;
++i;
}
cout<
2.双指针思想 ：15分
给链表放两个指针p和q：让两个指针间隔k个位置，一个动另一个也动，这样循环下去就能找到倒数第k个位置。 一开始只移动p，当i>k的时候才移动p
遍历了1 次：时间复杂度：0（n） 空间复杂度：0（1）
int find(LNode *L,int k){
LNode *p=L;
LNode *q=L->link; //q在p的后面
int i=1; //两个指针之间的初始距离
//两个指针同时移动
while(q){
q=q->link;
++i;
if(i>k) { p=p->link; }
}
//输出
if(p==L) {return 0;} //p指针未动过
else{
cout<
二.2010年
注意：1.时间空间都要高效
1.暴力解法：9分
创建虚拟数组（经常考）：先将前p个元素提取出来放入数组A，然后将剩下的元素往前移，最后再把数组A中的元素放到末尾。
移动后数组L前面的元素个数为：(n-1)-p+1=n-p;所以数组A插入的第一个位置是n-p
时间复杂度：0（n） 空间复杂度：0（p） //虚拟数组存放p个元素
//创建虚拟数组
//传了一个顺序表，顺序表和数组是一样的，但顺序表（结构体）有L.length,
//用数组的话还要提前定义数组长度n之类的
typedef struct Seqlist
{
int elem[100];//数组
int length;//数组长度
}Sqlist;
//这个表会变加&，反正加上准没错
//定义p（左移p个位置）
void remove(Sqlist &L, int p){
//定义虚拟数组（标准写法记下来）
int *A=(int *)malloc(sizeof(int)*p)； //这里的p代表长度
for(int i=0;i
2.最优解
分析：逆置前p个元素，再逆置后p个元素，最后一起逆置一遍
时间复杂度：0（n） 空间复杂度：0（1）
//逆置从m开始，n结束一段元素
void Reverse(Sqlist &L,int m,int n){
int mid=(m+n)/2; //因为只需要逆置一半元素
//逆置（交换）
for(int i=m,j=n;i<=mid;++i,--j){
int temp=L.data[i];
L.data[i]=L.data[j];
L.data[j]=temp;
}
}
//主函数
void change(Sqlist L,int p){
Reverse(L,0,P-1);
Reverse(L,p,L.length-1);
Reverse(L,0,L.length-1);
}
三.2011年
1.暴力解
分析：通过一 一对比（两个指针）合并两个序列，但又不需要完全合并完，只需要合并到中位数的地方
int merge(Sqlist A,Sqlist B){
int i=0, j=0;
//while(i
