思路：每次找出最小节点，删除并继续操作，直到整个链表为空，注意判断条件的变化
//19 循环单链表的最小值
void cycleListMinNode(LinkList &L){
//L的next不为空继续循环
while(L->next!=L){
//初始化四个节点，minnode保存最小值的节点，p保存当前节点，pre保存最小值的前驱，q保存前驱节点
LinkList pre=L,p=L->next,minpre=pre,minnode=p;
//循环遍历
while(p!=L){
//如果x比当前节点的值大，更新minnode
if(p->data < minnode->data){
//最小节点更新
minnode = p;
//最小前驱更新
minpre = pre;
}
//前驱更新
pre = p;
//继续遍历
p=p->next;
}
//删除操作
minpre->next = minnode->next;
//打印最小值节点
printf("%d,",minnode->data);
//释放最小值节点
free(minnode);
}
//释放链头
free(L);
}
题目： 单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点（ 通常单链表的最后一个结点的指针域是空的). 试编写算法判断单链表是否存在环。
思路：快慢指针，新建两个指针p，q，q比p始终快一个指针，若pq相遇则代表有环存在
//21环问题
bool islisthaveloop(LinkList &L){
//初始化节点
LinkList slow = L->next,fast = slow;
//链表遍历
while(fast){
//如果快慢指针相遇，则返回真
if(slow==fast){
return true;
}
//继续遍历后移
slow = slow->next;
//快指针每回移动2个位置
fast = fast->next->next;
}
//循环打破，链表没环，返回假
return false;
}
题目：〖2009 统考真题〗已知一个带有表头结点的单链表， 结点结构为data，next。
假设该链表只给出了头指针list. 在不改变链表的前提下， 请设计一个尽可能高效的算法， 查找链表中倒数第k个位置上的结点（k为正整数). 若查找成功，算法输出该结点的data 域的值，并返回1，否则，只返回0 。
思路： 新建两个指针p，q，p先向后移k个单位，然后pq一起移动，直到p为空，这个时候q指向的结点就为k了。
//22,09年真题
int findk(LinkList L,int k){
//设置次数计算
int count = 0;
//初始化节点
LinkList p = L->next,q = p;
//遍历链表
while(p){
//如果count小于k，也就是没达到k的位置，让p继续后移
if(countnext;
//计数加加
count++;
}else{
//p后移
p = p->next;
//q后移
q = q->next;
}
}
//如果count怎样都小于k，则数组长度不够，直接返回0
if(countdata);
return 1;
}
}
题目：〖2012 统考真题〗假定采用带头结点的单链表保存单词 当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如 “loading”和 “ being ”的存储映像如下图所示：设strl 和str2 分别指向两个单词所在单链表的头结点，链表结点结构为{data，*next}请设计一个时间上尽可能高效的算法， 找出由strl 和str2 所指向两个链表共同后缀的起始位置（ 如图中字符所在结点的位置p )
思路：计算两个链表长度，比较大小选出较长的链表，循环找到与短链表首个位置相同的节点，然后再一个个对比直到找到相同的节点即可！
//12年真题
LinkList sharewordspace(LinkList &str1,LinkList &str2){
//初始化两个链表的长度
int ls1=0,ls2=0;
//取别名，防止后续头节点被覆盖
LinkList s1 = str1,s2=str2;
//计算s1的长度
while(s1){
ls1++;
s1 = s1->next;
}
//计算s2的长度
while(s2){
ls2++;
s2 = s2->next;
}
//初始化长链表和短链表
LinkList shortList,longList;
//保存长度
int shortl,longl;
//对比哪个链表更长并装入对应节点中
if(s2>s1){
shortList = s1;
longList = s2;
longl = ls2;
shortl = ls1;
}else{
shortList = s2;
longList = s1;
longl = ls1;
shortl = ls2;
}
//计算距离
int distance = longl - shortl;
//长链表移动到短链表起始位置
while(longList && distance >0){
longList = longList->next;
distance--;
}
//寻找共用节点
while(longList && shortList){
if(longList == shortList)return longList;
longList = longList->next;
shortList = shortList->next;
}
//找不到返回空
return NULL;
}
题目：
【15年统考真题】 用单链表保存m个整数， 结点的结构为[data] [link], 且|data|<=n (n为正整数).现要求设计一个时间复杂度尽可能高效的算法， 对于链表中data 的绝对值相等的结点， 仅保留第一次出现的结点而删除其余绝对值相等的结点思路： 新建一个辅助数组，长度为n+1。若节点的绝对值出现过则值对应下标数组为1，若一为1则对节点删除。
//15年真题
void deletesamenode(LinkList &L,int n){
//数组开辟
int *a = (int*)malloc(sizeof(int)*(n+1));
//赋值数组，使下标为空
for(int i=0;inext,pre=L,r;
//中间变量x
int x;
//遍历链表p
while(p){
//获取节点值，赋值于x内
x = p->data;
//取x的绝对值
if(x<0)x=-x;
//判断数组内的x是否出现过
if(a[x]!=1){
//未出现过赋值1
a[x]=1;
//记录前驱
pre = p;
//继续后移
p = p->next;
}else{
//删除操作，保存节点
r = p;
//前驱后移
pre->next = p->next;
//节点后移
p = p->next;
//释放节点
free(r);
}
}
}
题目： [ 2019 统考真题] 设线性表L=（a1,a2,a3...,an-2,an-1,an) 采用带头结点的单链表保存，表中的结点定义如下：typedef struct node
{ int data；
Struct node*next；
} NODE;
请设计一个空间复杂度为o(1) 且时间上尽可能高效的算法, 重新排列L中的各结点,得到线性表：(a1,an,a2,an-1,a3,an-2....)
要求：
1 ） 给出算法的基本设计思想·
2 ） 根据设计思想， 采用C 或C + + 语言描述算法， 关键之处给出注释·
3 〕说明你所设计的算法的时间复杂度·
思路：先计算长度，取中间节点位置，将链表分为a,b两段，对b链表逆转然后再插入a中，接到L上。
//19年真题
void resortLinkList(LinkList &L){
if(L->next == NULL)return;
//长度初始化
int length = 0,count = 0;
//初始化节点
LinkList p = L->next,a,b,temp,pre,r;
//计算长度
while(p){
length++;
p = p->next;
}
//取中间值节点的地址
p = L->next;
while(count < length/2){
count ++;
p = p->next;
}
//将中间节点放入p
b = p;
//前驱设为b
pre = b;
//b后移
b = b->next;
//置首个节点为空
pre->next = NULL;
//b逆转
while(b){
temp = b->next;
b->next = pre;
pre = b;
b = temp;
}
//得到被反转的首个节点
b = pre;
//a指向前有序的节点
a = L->next;
//先将L置为空
L->next = NULL;
//r作为前驱指向L
r = L;
//遍历开始
while(a && b && length>0){
//奇偶判断
if(length %2 != 0){
//p保存后继防止断链
p = b->next;
//后插法，置当前节点的next为空
b->next = NULL;
//前驱指向当前节点
r->next = b;
//前驱更新
r = b;
//b链后移
b = p;
}else{
//p保存后继防止断链
p = a->next;
//后插法，置当前节点的next为空
a->next = NULL;
//前驱指向当前节点
r->next = a;
//前驱更新
r = a;
//a链后移
a = p;
}
//长度更新
length--;
}
}
以上代码仅供参考，如有错误还请指正，谢谢！
