删除链表的倒数第n个节点_牛客题霸_牛客网思路快慢指针法1.定义两个指针fast,slow2.要删除链表倒数第n个元素让fast先走n步3.然后slow和fast一起走直到fast-NULL此时slow-next就是要删除的元素5.返回删除后的节点6.特殊情况链表为空或不删除元素structListNode*removeNthFromEnd(structListNode*head,intn){// write code here//双指针法if(headNULL||n0)returnhead;structListNode*fasthead;structListNode*slowhead;//1.让fast先走n步for(inti0;in;i){if(fastNULL)returnhead;//n 链表长度返回原链表fastfast-next;}//特殊情况fastNULL删除首元素if(fastNULL){structListNode*temphead;headhead-next;free(temp);tempNULL;returnhead;}//3.然后slow和fast一起走直到fast-nextNULL此时slow-next就是要删除的元素while(fast-next!NULL){fastfast-next;slowslow-next;}//4.逻辑上删除slow-nextfree(slow-next)并指空structListNode*tempslow-next;slow-nextslow-next-next;free(temp);tempNULL;//5.返回删除后的节点returnhead;}反转链表 _牛客网思路三指针法1.定义三个指针pre、cur、nex2.遍历链表通过这三个指针改变链表之间的指向3.让cur-nextpre进行反转,在这之前需要提前保存next4.改变方向后pre和cur同时后移动5.直到curnull,说明反转完成pre就是新的头节点6.返回新的头节点structListNode*ReverseList(structListNode*head){// write code hereif(headNULL)returnNULL;//链表为空structListNode*preNULL;structListNode*curhead;while(cur){structListNode*nexcur-next;//保存cur-nextcur-nextpre;//反转precur;//后移curnex;}returnpre;}思路头插法1.定义三个指针pre、cur、nex2.遍历链表将当前元素的下一个节点插到最头部直到链表结束反转完成3.因为每次头插头节点一直在改变所以定义一个虚拟头节点dummy让其指向新头插的节点4.头插首先用指针nex保存cur-next;其次让cur-next指向cur-next-next;然后将nex插到pre和头之间最后重复此操作5.返回新的头节点dummy-next;6.特殊情况链表为空structListNode*ReverseList(structListNode*head){if(headNULL)returnNULL;//链表为空structListNodedummy{-1,NULL};//虚拟头节点structListNode*predummy;pre-nexthead;structListNode*curhead;while(cur-next){structListNode*nexcur-next;cur-nextcur-next-next;nex-nextpre-next;pre-nextnex;}returndummy.next;链表内指定区间反转 _牛客网思路头插法1.将第m个节点后的n-m个节点插到m前面2.定义一个指针pre让其走到第m-1个节点3.定义一个指针cur,cur为第m个节点定义一个指针nex,用来保存cur-next4.将nex插到pre后面进行n-m次实现反转5.返回头节点6.注意判断传入数据是否合法7.特殊情况m1时头节点会丢失可定义一个虚拟头节点保存头节点structListNode*reverseBetween(structListNode*head,intm,intn){// write code hereif(head0||m0)returnhead;structListNodedummy{0,NULL};dummy.nexthead;//定义一个虚拟头节点保存头节点structListNode*predummy;for(inti1;im;i){//让pre走到第m-1个节点prepre-next;}structListNode*curpre-next;//cur是要开始反转的起始位置for(inti0;in-m;i){//将cur后面的n-m个元素挨个插到最前面structListNode*nexcur-next;cur-nextcur-next-next;nex-nextpre-next;pre-nextnex;}returndummy.next;//返回头节点}链表的中间节点 _力扣思路双指针法1.定义快慢指针slow、fast2.遍历链表slow走一步、fast走两步3.当fastNULL、fast最后一个节点时slow就是链表的中间节点4.返回中间节点5.特殊情况链表为空structListNode*middleNode(structListNode*head){if(headNULL)returnNULL;structListNode*slowhead;structListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}returnslow;}删除链表的中间节点思路双指针法1.找到中间节点的前一个结点让这个节点指向中间节点的下一个节点在逻辑上删除中间节点2.定义一个虚拟头节点dummy和快慢指针fast/slow3.让slowdummyfasthead, slow走一步fast走两步4.遍历链表slow指向的就是中间节点的前一个节点逻辑上删除中间节点。5.返回头节点6.特殊情况链表为空或只有一个节点把这个节点freestructListNode*deleteMiddle(structListNode*head){if(NULLhead)returnNULL;//链表为空structListNodedummy{0,NULL};//虚拟头节点dummy.nexthead;if(head-nextNULL){//只有一个节点free(head);returnNULL;}structListNode*slowdummy;structListNode*fasthead;while(fastfast-next){//找到中间节点的前一个节点slowslow-next;fastfast-next-next;}structListNode*tempslow-next;//保存中间节点slow-nextslow-next-next;//逻辑上删除中间节点free(temp);//删除中间节点returnhead;}判断一个链表是否为回文结构思路反转链表双指针1.反转后半部分链表从头尾遍历一一比对判断是否是回文结构2.首先找到链表的中间节点3.然后反转链表的后半部分4.最后从头、尾遍历链表至中间部分若有节点数据不同则不是回文结构5.特殊情况链表为空或者单节点boolisPail(structListNode*head){//链表为空或单节点if(NULLhead||head-nextNULL){returntrue;}//1.找到中间节点structListNode*slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}//slow即为中间节点//2.反转链表后半部分structListNode*preNULL;structListNode*curslow;while(cur){structListNode*nexcur-next;cur-nextpre;precur;curnex;}//前后遍历链表判断回文结构while(pre!NULL){if(pre-val!head-val){returnfalse;}headhead-next;//移动前半部分prepre-next;//移动后半部分}returntrue;}链表中的节点每k个一组翻转思路1.遍历链表检查是否有k个元素2.有则反转否则退出循环3.反转一组结束后要更新pre、cur;让pre指向当前反转的最后一个节点cur指向要反转的下一组的第一个节点4.循环结束返回新的头节点5.注意要检验链表为空和参数k的合法性structListNode*reverseKGroup(structListNode*head,intk){// write code here//检查链表是否为空和参数k合法性if(headNULL||k1)returnhead;//定义虚拟头节点structListNodedummy{0,NULL};dummy.nexthead;structListNode*predummy;structListNode*curhead;//遍历链表while(1){structListNode*checkpre;intflag0;for(inti0;ik;i){//检查链表元素是否kcheckcheck-next;if(checkNULL){flag1;break;}}if(flag)break;//节点不足退出循环for(inti1;ik;i){//反转一组structListNode*nexcur-next;cur-nextcur-next-next;nex-nextpre-next;pre-nextnex;}precur;//反转后的最后一个节点curcur-next;//指向新的要反转的一组}returndummy.next;//返回新的头节点}判断链表中是否有环思路快慢指针1.fast每次走两步slow每次走一步2.fast和slow相遇了则代表链表有环(若是有环链表slow进入环内fast每走一次与slow的距离就减一)boolhasCycle(structListNode*head){// write code herestructListNode*fasthead,*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow)returntrue;}returnfalse;}链表中环的入口结点思路1.快慢指针找相遇点2.双指针同步找入环口3.返回环的入口结点structListNode*EntryNodeOfLoop(structListNode*pHead){// write code hereif(pHeadNULL||pHead-nextNULL)returnNULL;structListNode*slowpHead,*fastpHead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){fastpHead;while(1){if(fastslow){returnfast;}fastfast-next;slowslow-next;}}}returnNULL;}删除有序链表中重复的元素-I双指针法1.遍历链表slow-head/fast-head-next2.判断元素是否重复若重复则删除fast后移删除所有当前重复的元素3.当slow和fast不同时slow和fast同时后移继续删除下一个 重复元素4.特殊情况链表为空或单节点structListNode*deleteDuplicates(structListNode*head){// write code hereif(headNULL||head-nextNULL)returnhead;structListNode*slowhead;structListNode*fastslow-next;while(fast){if(slow-valfast-val){structListNode*tempfast;slow-nextfast-next;fastfast-next;free(temp);tempNULL;continue;}slowslow-next;fastfast-next;}returnhead;}