手机可以制作网站吗,外贸建站主机空间哪家好,一般通过什么渠道了解防灾减灾知识?(可多选),dz可以做门户网站吗#x1f525;博客主页#xff1a;小王又困了
#x1f4da;系列专栏#xff1a;数据结构
#x1f31f;人之为学#xff0c;不日近则日退
❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 目录
一、移除链表元素
#x1f4a1;方法一#xff1a;
#x1f4a1;方法二… 博客主页小王又困了
系列专栏数据结构
人之为学不日近则日退
❤️感谢大家点赞收藏⭐评论✍️ 目录
一、移除链表元素
方法一
方法二
二、链表的中间节点
方法一
三、链表中倒数第k个结点
方法一
四、反转链表
方法一
方法二
五、合并两个有序链表
方法一 ️前言 在上一期中我们给大家介绍了单链表也了解了单链表的实现。接下来就让我们进入实践练习一些经典题目让我们对单链表的理解更加深入。 一、移除链表元素
题目 方法一 我们使用两个指针遍历数组遇到与 val 相同的数据域就删除这个节点。我们在思考问题时要想全面当要删除头节点时常规方法就无法实现对于删除头节点要做单独处理。 常规删除 头节点删除 struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* prevNULL;struct ListNode* curhead;while(cur!NULL){//删除if(valcur-val){//头删if(curhead){headcur-next;free(cur);curhead;}//常规else{prev-nextcur-next;free(cur);curprev-next;}}//遍历else{prevcur;curcur-next;}}return head;
} 方法二 我们通过遍历把节点的数据域不等于val的节点尾接到新的链表中。我们要考虑第一个节点是不是要删除的。最后一个节点的指针域置空要放在循环结束后判断tail是否为空指针。 struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* newheadNULL;struct ListNode* tailNULL;struct ListNode* curhead;while(cur){if(cur-nextval){//删除struct ListNode* delcur;curcur-next;free(del);}else{//尾插if(tailNULL){newheadtailcur;//tailcur;}else{tail-nextcur;tailtail-next; }curcur-next;}}if(tail){tail-nextNULL;}return newhead;
} 二、链表的中间节点
题目 方法一 我们可以定义两个指针快指针一次走两步慢指针一次走一步当快指针走到结尾时慢指针正好走了一半这样我们就可以找到中间节点。 struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;
} 三、链表中倒数第k个结点
题目 方法一 我们可以参考上一题的方法同样定义快慢指针想让快指针走k步然后在同时走走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点所以我们要加入判断。 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* fastpListHead;struct ListNode* slowpListHead;while(k--){//链表没有k步长if(fastNULL){return NULL;}fastfast-next;}while(fast!NULL){fastfast-next;slowslow-next;}return slow;
} 四、反转链表
题目 方法一 我们定义三个指针n1,n2,n3来改变节点链接的顺序。将头节点变为尾节点当n2为空指针时n1就为链表的头节点只需返回n1就可以。两个指针倒方向一个指针保持下一个。 struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* n1NULL;struct ListNode* n2head;struct ListNode* n3;if(n2){n3n2-next;}while(n2){n2-nextn1;//往后走n1n2;n2n3;if(n3){n3n3-next;}}return n1;
} 方法二 将链表的节点一个一个拿下来进行头插。这里要注意赋值的顺序。 struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* curhead;struct ListNode* newnodeNULL;while(cur){//保存节点struct ListNode* nextcur-next;//头插cur-nextnewnode;newnodecur;curnext;}return newnode;
} 五、合并两个有序链表
题目 方法一 我们创建一个带哨兵位的链表这样在尾插时就不用判断是否是第一个节点可以提高效率。要记住在最后要将哨兵位的空间释放。 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1NULL){return list2;}if(list2NULL){return list1;}struct ListNode* headNULL;struct ListNode* tailNULL;//创建一个哨兵位headtail(struct ListNode*)malloc(sizeof(struct ListNode));while(list1list2){if(list1-vallist2-val){tail-nextlist1;tailtail-next;list1list1-next;}else{tail-nextlist2;tailtail-next;list2list2-next;}}if(list1){tail-nextlist1;}if(list2){tail-nextlist2;}struct ListNode* delhead;headhead-next;free(del);return head;
} 本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位读者三连支持。文章有问题可以在评论区留言博主一定认真认真修改以后写出更好的文章。你们的支持就是博主最大的动力。
