当前位置：首页 > news >正文

链表（牛客网编程练习）

news 2026/8/14 15:45:56

删除链表的倒数第n个节点_牛客题霸_牛客网

1.定义两个指针fast,slow
2.要删除链表倒数第n个元素：让fast先走n步
3.然后，slow和fast一起走，直到fast->NULL，此时slow->next就是要删除的元素``
5.返回删除后的节点
6.特殊情况：链表为空或不删除元素

structListNode*removeNthFromEnd(structListNode*head,intn){// write code here//双指针法if(head==NULL||n<=0)returnhead;structListNode*fast=head;structListNode*slow=head;//1.让fast先走n步for(inti=0;i<n;i++){if(fast==NULL)returnhead;//n > 链表长度，返回原链表fast=fast->next;}//特殊情况fast==NULL，删除首元素if(fast==NULL){structListNode*temp=head;head=head->next;free(temp);temp=NULL;returnhead;}//3.然后，slow和fast一起走，直到fast->next==NULL，此时slow->next就是要删除的元素while(fast->next!=NULL){fast=fast->next;slow=slow->next;}//4.逻辑上删除slow->next，free(slow->next)并指空structListNode*temp=slow->next;slow->next=slow->next->next;free(temp);temp=NULL;//5.返回删除后的节点returnhead;}

反转链表 _牛客网

思路：三指针法
1.定义三个指针pre、cur、nex
2.遍历链表，通过这三个指针改变链表之间的指向
3.让cur->next=pre进行反转,在这之前需要提前保存next
4.改变方向后，pre和cur同时后移动
5.直到cur==null,说明反转完成，pre就是新的头节点
6.返回新的头节点

structListNode*ReverseList(structListNode*head){// write code hereif(head==NULL)returnNULL;//链表为空structListNode*pre=NULL;structListNode*cur=head;while(cur){structListNode*nex=cur->next;//保存cur->nextcur->next=pre;//反转pre=cur;//后移cur=nex;}returnpre;}

思路：头插法
1.定义三个指针pre、cur、nex
2.遍历链表，将当前元素的下一个节点插到最头部，直到链表结束，反转完成
3.因为每次头插，头节点一直在改变，所以定义一个虚拟头节点dummy，让其指向新头插的节点
4.头插：首先，用指针nex保存cur->next;
其次，让cur->next指向cur->next->next;
然后，将nex插到pre和头之间
最后，重复此操作
5.返回新的头节点dummy->next;
6.特殊情况：链表为空

structListNode*ReverseList(structListNode*head){if(head==NULL)returnNULL;//链表为空structListNodedummy={-1,NULL};//虚拟头节点structListNode*pre=&dummy;pre->next=head;structListNode*cur=head;while(cur->next){structListNode*nex=cur->next;cur->next=cur->next->next;nex->next=pre->next;pre->next=nex;}returndummy.next;

链表内指定区间反转 _牛客网

思路：头插法
1.将第m个节点后的n-m个节点插到m前面
2.定义一个指针pre，让其走到第m-1个节点
3.定义一个指针cur,cur为第m个节点；定义一个指针nex,用来保存cur->next
4.将nex插到pre后面，进行n-m次，实现反转
5.返回头节点
6.注意判断传入数据是否合法
7.特殊情况：m==1时，头节点会丢失，可定义一个虚拟头节点，保存头节点

structListNode*reverseBetween(structListNode*head,intm,intn){// write code hereif(head==0||m<=0)returnhead;structListNodedummy={0,NULL};dummy.next=head;//定义一个虚拟头节点，保存头节点structListNode*pre=&dummy;for(inti=1;i<m;i++){//让pre走到第m-1个节点pre=pre->next;}structListNode*cur=pre->next;//cur是要开始反转的起始位置for(inti=0;i<n-m;i++){//将cur后面的n-m个元素挨个插到最前面structListNode*nex=cur->next;cur->next=cur->next->next;nex->next=pre->next;pre->next=nex;}returndummy.next;//返回头节点}

链表的中间节点 _力扣

思路：双指针法
1.定义快慢指针slow、fast
2.遍历链表，slow走一步、fast走两步
3.当fast==NULL、fast=最后一个节点时，slow就是链表的中间节点
4.返回中间节点
5.特殊情况：链表为空

structListNode*middleNode(structListNode*head){if(head==NULL)returnNULL;structListNode*slow=head;structListNode*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}returnslow;}

删除链表的中间节点

思路：双指针法
1.找到中间节点的前一个结点，让这个节点指向中间节点的下一个节点，在逻辑上删除中间节点
2.定义一个虚拟头节点dummy和快慢指针fast/slow
3.让slow=dummy，fast=head, slow走一步，fast走两步
4.遍历链表，slow指向的就是中间节点的前一个节点，逻辑上删除中间节点。
5.返回头节点
6.特殊情况：链表为空或只有一个节点（把这个节点free）

structListNode*deleteMiddle(structListNode*head){if(NULL==head)returnNULL;//链表为空structListNodedummy={0,NULL};//虚拟头节点dummy.next=head;if(head->next==NULL){//只有一个节点free(head);returnNULL;}structListNode*slow=&dummy;structListNode*fast=head;while(fast&&fast->next){//找到中间节点的前一个节点slow=slow->next;fast=fast->next->next;}structListNode*temp=slow->next;//保存中间节点slow->next=slow->next->next;//逻辑上删除中间节点free(temp);//删除中间节点returnhead;}

判断一个链表是否为回文结构
思路：反转链表（双指针）
1.反转后半部分链表，从头尾遍历，一一比对，判断是否是回文结构
2.首先，找到链表的中间节点
3.然后，反转链表的后半部分
4.最后，从头、尾遍历链表至中间部分，若有节点数据不同则不是回文结构
5.特殊情况：链表为空或者单节点

boolisPail(structListNode*head){//链表为空或单节点if(NULL==head||head->next==NULL){returntrue;}//1.找到中间节点structListNode*slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}//slow即为中间节点//2.反转链表后半部分structListNode*pre=NULL;structListNode*cur=slow;while(cur){structListNode*nex=cur->next;cur->next=pre;pre=cur;cur=nex;}//前后遍历链表，判断回文结构while(pre!=NULL){if(pre->val!=head->val){returnfalse;}head=head->next;//移动前半部分pre=pre->next;//移动后半部分}returntrue;}

链表中的节点每k个一组翻转
思路：
1.遍历链表，检查是否有k个元素
2.有则反转，否则退出循环
3.反转一组结束后，要更新pre、cur;让pre指向当前反转的最后一个节点，cur指向要反转的下一组的第一个节点
4.循环结束，返回新的头节点
5.注意：要检验链表为空和参数k的合法性

structListNode*reverseKGroup(structListNode*head,intk){// write code here//检查链表是否为空和参数k合法性if(head==NULL||k<=1)returnhead;//定义虚拟头节点structListNodedummy={0,NULL};dummy.next=head;structListNode*pre=&dummy;structListNode*cur=head;//遍历链表while(1){structListNode*check=pre;intflag=0;for(inti=0;i<k;i++){//检查链表元素是否>=kcheck=check->next;if(check==NULL){flag=1;break;}}if(flag)break;//节点不足，退出循环for(inti=1;i<k;i++){//反转一组structListNode*nex=cur->next;cur->next=cur->next->next;nex->next=pre->next;pre->next=nex;}pre=cur;//反转后的最后一个节点cur=cur->next;//指向新的要反转的一组}returndummy.next;//返回新的头节点}

判断链表中是否有环
思路：快慢指针
1.fast每次走两步，slow每次走一步
2.fast和slow相遇了，则代表链表有环
(若是有环链表，slow进入环内，fast每走一次与slow的距离就减一)

boolhasCycle(structListNode*head){// write code herestructListNode*fast=head,*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow)returntrue;}returnfalse;}

链表中环的入口结点
思路：
1.快慢指针找相遇点
2.双指针同步找入环口
3.返回环的入口结点

structListNode*EntryNodeOfLoop(structListNode*pHead){// write code hereif(pHead==NULL||pHead->next==NULL)returnNULL;structListNode*slow=pHead,*fast=pHead;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){fast=pHead;while(1){if(fast==slow){returnfast;}fast=fast->next;slow=slow->next;}}}returnNULL;}

删除有序链表中重复的元素-I
双指针法：
1.遍历链表：slow->head/fast->head->next
2.判断元素是否重复，若重复则删除，fast后移，删除所有当前重复的元素
3.当slow和fast不同时，slow和fast同时后移，继续删除下一个重复元素
4.特殊情况：链表为空或单节点

structListNode*deleteDuplicates(structListNode*head){// write code hereif(head==NULL||head->next==NULL)returnhead;structListNode*slow=head;structListNode*fast=slow->next;while(fast){if(slow->val==fast->val){structListNode*temp=fast;slow->next=fast->next;fast=fast->next;free(temp);temp=NULL;continue;}slow=slow->next;fast=fast->next;}returnhead;}