网络科技公司 网站建设,济南网站建设流程,wordpress不能连接数据库,wordpress用户注册邮箱验证文章目录 总结01 递归删除结点02 删除结点03 反向输出04 删除最小值05 逆置06 链表递增排序07 删除区间值08 找公共结点09 增序输出链表10 拆分链表--尾插11 拆分链表--头插12 删除相同元素13 合并链表14 生成含有公共元素的链表C15 求并集16 判断子序列17 判断循环链表是否对称… 文章目录 总结01 递归删除结点02 删除结点03 反向输出04 删除最小值05 逆置06 链表递增排序07 删除区间值08 找公共结点09 增序输出链表10 拆分链表--尾插11 拆分链表--头插12 删除相同元素13 合并链表14 生成含有公共元素的链表C15 求并集16 判断子序列17 判断循环链表是否对称18 两个循环链表链接19 找最小结点并删除21 判断单链表是否有环22 【2009真题】找倒数第k个元素23 【2012真题】相同后缀找起始位置24 【2015真题】删除绝对值相同25 【2019真题】重新排列链表 总结
删除结点1、2、4就地逆置5、合并链表分解链表10、11、去除重复元素12、并集14、15循环链表17、18、19、20头插法、尾插法重点基础必掌握。判断是否有环21
01 递归删除结点
用函数递归调用删除结点。
void deletex(linklist L,int x){if(LNULL) return;lnode *p;if(L-datax){pL;LL-next;free(p);deletex(L,x);}else deletex(L-next,x);
}02 删除结点
注意删除结点的时候可能断链。
void deletex2(linklist L,int x){lnode *pL-next,*preL,*q;while(p){if(p-datax){qp;pp-next;pre-nextp;free(q);}else{prep;pp-next;}}
}03 反向输出
利用函数调用的特性反向输出。
void r_print(linklist L){if(L!NULL){r_print(L-next);cout(L-data) ;}else return;
}
void r_ignore_node(linklist L){if(L-next!NULL){r_print(L-next);}
}04 删除最小值
设置保留最小值的指针和其前驱每次更新最小值
void delete_min(linklist L){lnode *pL-next,*preL;lnode *minpp,*minprepre;while(p){if(p-dataminp-data){minpp;minprepre;}else{pp-next;prepre-next;}}minpre-nextminp-next; //删除最小值结点free(minp);
}05 逆置
很重要的基础头插法
void head(linklist L){lnode *pL-next,*r;L-nextNULL;while(p){rp-next; //记录下一结点p-nextL-next;L-nextp;pr;}
}06 链表递增排序
使用插入排序的思想将头置空之后扫描最小元素然后使用尾插法插入头中。
void insert_sort(linklist L){lnode *pL-next,*rp-next,*pre;p-nextNULL;pr;while(p){rp-next;preL;while(pre-next!NULLpre-next-datap-data){prepre-next;}p-nextpre-next;pre-nextp;pr;}
}07 删除区间值
见2题的删除代码改下if语句即可。
void delete_x_m_n(linklist L,int m, int n){lnode *pL-next,*preL,*q;while(p){if(p-datanp-datam){qp;pp-next;pre-nextp;free(q);}else{prep;pp-next;}}
}08 找公共结点
linklist find_same_dot(linklist L1,linklist L2){linklist longlist, shortlist;int dist0;int len1length(L1),len2length(L2);if(len1len2){longlistL1;shortlistL2;distlen1-len2;}else{longlistL2;shortlistL1;distlen2-len1;}while(dist--) longlistlonglist-next;while(longlist){if(longlist-datashortlist-datalonglist-next-datashortlist-next-data)return longlist;else{longlistlonglist-next;shortlistshortlist-next;}}return NULL;
}09 增序输出链表
见6题
void min_output(linklist L){while(L-next){lnode *preL,*pL-next;lnode *minprepre, *minpp;while(p){if(p-dataminp-data){minpp;minprepre;}pp-next;prepre-next;}coutminp-data ;minpre-nextminp-next;free(minp);}
}10 拆分链表–尾插
第一种方法是在A中直接删除。
linklist split_1_1(linklist A){linklist B (linklist)malloc(sizeof(lnode));B-nextNULL;lnode *pA-next,*raA;lnode *rbB,*q;while(p){//向后移一个rap;pp-next;//从A中删除结点qp;ra-nextp-next;pp-next;//利用尾插法将结点插入B中rb-nextq;rbrb-next;}ra-nextNULL;rb-nextNULL;return B;
}第二种方法是把A的头拿下来再选最小的排在A后。尾插
linklist split_1_2(linklist A){linklist B (linklist)malloc(sizeof(lnode));B-nextNULL;lnode *pA-next,*raA;lnode *rbB;//把表头摘下来A-nextNULL;while(p){//结点给Ara-nextp;rara-next;pp-next;//结点给Brb-nextp;rbrb-next;pp-next;}ra-nextNULL;rb-nextNULL;return B;
}11 拆分链表–头插
第一种方法同上
linklist split_1_1(linklist A){linklist B (linklist)malloc(sizeof(lnode));B-nextNULL;lnode *pA-next,*raA;lnode *rbB,*q;while(p){//向后移一个rap;pp-next;//从A中删除结点qp;ra-nextp-next;pp-next;//利用头插法将结点插入B中qp-next;p-nextrb-next;rb-nextp;pq;}ra-nextNULL;return B;
}第二种方法同上
linklist split_2_1(linklist A){linklist B (linklist)malloc(sizeof(lnode));B-nextNULL;lnode *pA-next,*raA;lnode *rbB,*q;//把表头摘下来A-nextNULL;while(p){//结点给Ara-nextp;rara-next;pp-next;//结点给Bif(p){qp-next;p-nextrb-next;rb-nextp;pq;}}ra-nextNULL;//b是头插法所以最后指向是为NULLreturn B;
}12 删除相同元素
简单代码只不过要注意的p是要删除结点的前一个结点判断的时候别判断错了。
void del_same(linklist L){lnode *pL-next,*q;if(pNULL) return;while(p-next){qp-next;if(p-dataq-data){p-nextq-next;free(q);}else{pp-next;}}
}13 合并链表
void merge(linklist L1,linklist L2)
{lnode *p1L1-next,*p2L2-next,*r;L1-nextNULL;while(p1p2){if(p1-datap2-data){rp1-next;p1-nextL1-next;L1-nextp1;p1r;}else{rp2-next;p2-nextL1-next;L1-nextp2;p2r;}}if(p1) p2p1;while(p2){rp2-next;p2-nextL1-next;L1-nextp2;p2r;}free(L2);
}14 生成含有公共元素的链表C
两个链表分别遍历比较值头插入C中
linklist merge_same(linklist A,linklist B){lnode *pA-next,*qB-next;lnode *r,*s;linklist C (linklist)malloc(sizeof(lnode));rC;while(pq){if(p-dataq-data){pp-next;}else if(p-dataq-data){qq-next;}else{s(lnode *)malloc(sizeof(lnode *));s-datap-data;r-nexts;rr-next;pp-next;qq-next;}}r-nextNULL;return C;
}15 求并集
值不相同时分别删除A和B中的值相同时删除B中的值基础就是删除代码
void intersection(linklist A,linklist B){lnode *pA-next,*qB-next;lnode *rA,*temp;while(pq){if(p-dataq-data){tempp;pp-next;free(temp);}else if(p-dataq-data){tempq;qq-next;free(temp);}else{//相等的时候保留A中相同元素r-nextp;rr-next;pp-next;//删除B中相同的元素tempq;qq-next;free(temp);}}while(p){tempp;pp-next;free(temp);}while(q){tempq;qq-next;free(temp);}r-nextNULL;
}16 判断子序列
朴素kmp也有所说bf的
bool simple_kmp(linklist A,linklist B){lnode *pA-next,*qB-next,*rA-next;while(pq){if(p-data!q-data){rr-next;pr;qA-next;}else{pp-next;qq-next;}}if(q) return false;else return true;
}17 判断循环链表是否对称
循环链表就方便了能找前驱和后继两个指针同时移动判断值即可。
bool symmetry(linklist L)
{lnode *pL-next,*qL-prior;while(p!qq-next!p){if(p-dataq-data){pp-next;qq-prior;}else return false;}return true;
}18 两个循环链表链接
注意头尾即可
void add(linklist h1,linklist h2)
{lnode *ph1-next,*qh2-next;while(p-next!h1){pp-next;}while(q-next!h2){qq-next;}p-nexth2-next;//初始化的链表带头结点若不带h2即可q-nexth1;
}19 找最小结点并删除
遍历链表每次输出最小结点然后删除即可 相同代码见9题
void find_min(linklist L){while(L-next!L){lnode *preL,*pL-next;lnode *minprepre, *minpp;while(p!L){if(p-dataminp-data){minpp;minprepre;}pp-next;prepre-next;}coutminp-data ;minpre-nextminp-next;free(minp);}free(L);
}21 判断单链表是否有环
两步走总能相遇按照这个作为遇到的条件找相遇点和入环结点。 25题也是两步走。
lnode* findd(lnode *L)
{lnode *fL,*sL;while(s!NULLf-next!NULL){ss-next;ff-next-next;if(s-dataf-data) break; //可以直接设置指针但是我初始化的有单链表为int a[15]{1,2,3,4,5,6,7,8,9,4,5,6,7,8,9};故用这种方法}if(sNULL||f-nextNULL) return NULL;lnode *pL,*qs;while(p-data!q-data){pp-next;qq-next;}return p;
}22 【2009真题】找倒数第k个元素
相当于用长度为k的尺子比着找最右端到尾部的时候最左端就是倒数第k个元素。
int findk(linklist L, int k){lnode *pL,*qL;int count0;while(p){if(countk) count;else qq-next;pp-next;}if(countk) return 0;else coutkth to last position: q-data;return 1;
}23 【2012真题】相同后缀找起始位置
把尾部排齐两个指针遍历链表长度相同时找到相同时尾部对齐了排齐之后遍历两个链表找第一个不相同的位置该位置的下一个位置就是相同后缀的位置
typedef struct lnode{int data;struct lnode *next;
}lnode,*linklist;
lnode * find_addr(linklist str1, linklist str2){lnode *p,*q;int mlength(str1);int nlength(str1);for(pstr1;mn;m--) pp-next;for(qstr2;mn;n--) qq-next;while (p-next!NULLq-next!NULL){pp-next;qq-next;}return p-next;
}24 【2015真题】删除绝对值相同
要求时间复杂度尽可能高➡️空间换时间
数组存查找状态0表示绝对值未找到1表示找到第二次找到的同时删除该结点注意动态分配数组的使用静态数组试了试内存超出不知道是不是这个问题
void same(linklist L,int n)
{lnode *pL;int *q;q(int *)malloc(sizeof(int)*(n1));for(int i0;in1;i) *(qi)0;int s;lnode *f;while(p-next!NULL){sabs(p-next-data);if(*(qs)0) {*(qs)1;pp-next;}else{fp-next;p-nextf-next;free(f);}}free(q);
}25 【2019真题】重新排列链表
两步走找中间结点逆置后边链表使用头插法看成两个链表进行插入 21也是两步走
void change(linklist L){lnode *p,*q,*r,*s;pqL;while (q-next){pp-next;qq-next;if(q-next) qq-next;}qp-next; //p现在在中间结点p-nextNULL; //把后半段摘下来逆置之后分别遍历两个链表插入指定位置while (q) //头插法实现原地逆置{rq-next; //暂存后继结点q-nextp-next; //将q结点放在头结点p之后p-nextq;qr;}sL-next; //插入点qp-next; //后半段数据点p-nextNULL; while(q){rq-next;q-nexts-next;s-nextq;sq-next;qr;}
}
