模板网站能用吗,安徽住房建设厅官网,网站从建设到运行要多少钱,如何制作一个电脑软件#x1f525;博客主页#xff1a; 小羊失眠啦. #x1f3a5;系列专栏#xff1a;《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 文章目录 前言一、移除链表元素二、寻找链表中间结点三、输出链表倒数第k个结点四、反转单链表五… 博客主页 小羊失眠啦. 系列专栏《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞收藏⭐评论✍️ 文章目录 前言一、移除链表元素二、寻找链表中间结点三、输出链表倒数第k个结点四、反转单链表五、合并两个有序链表 前言 在上一期中我们介绍了单链表也对单链表的实现进行具体的了解接下来我们开始单链表的练习对单链表更深层的理解让小伙伴们灵活的使用单链表话不多说开造~ 一、移除链表元素 方法一
我们使用两个指针遍历数组遇到与 val 相同的结点时就删除这个节点。我们在思考问题时要想全面当要删除头节点时常规方法就无法实现对于删除头节点要做单独处理。
常规删除 头节点删除 思路(1)首先给出判断cur是否是空的不是空的之后判断是否有val有的话就判断是否在头部是的话一种情况不是的话又是一种情况。2第一种情况题意所给出的情况第二种情况中间连续个value前两种可以合并第三种情况一开始就出现6或者连续个6第四种情况空的
struct ListNode* removeElements(struct ListNode* head, int val)
{if (head NULL)return head;struct ListNode* prev NULL, * cur head;while (cur){struct ListNode* Next cur-next;if (cur-val val){if (prev NULL){head Next;cur Next;}else{prev-next Next;free(cur);cur Next;}}else{prev cur;cur Next;}}return head;
}方法二
我们通过遍历把节点的数据域不等于val的节点尾接到新的链表中。我们要考虑第一个节点是不是要删除的。最后一个节点的指针域置空要放在循环结束后判断tail是否为空指针。 truct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newnodeNULL;struct ListNode* curhead,*tailnewnode;while(cur){if(cur-val!val){if(tailNULL){newnodecur;tailnewnode;}else{tail-nextcur;tailtail-next;}curcur-next;}else{struct ListNode* delcur;curcur-next;free(del);}}if(tail){tail-nextNULL;}return newnode;
}二、寻找链表中间结点 我们可以定义两个指针快指针一次走两步慢指针一次走一步当快指针走到结尾时慢指针正好走了一半这样我们就可以找到中间节点。 struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slowhead,*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}三、输出链表倒数第k个结点 我们可以参考上一题的方法同样定义快慢指针先让快指针走k步然后再同时走走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点所以我们要加入判断。 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slowpListHead,*fastpListHead;while(k--){if(fastNULL){return NULL;}fastfast-next;}while(fast){slowslow-next;fastfast-next;}return slow;
}四、反转单链表 方法一
我们定义三个指针n1,n2,n3来改变节点链接的顺序。将头节点变为尾节点当n2为空指针时n1就为链表的头节点只需返回n1就可以。两个指针倒方向一个指针保持下一个。
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* n1NULL,*n2head,*n3NULL;if(headNULL)return head;while(n2){n3n2-next;n2-nextn1;n1n2;n2n3;}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;while(list1list2){if((list1-val) (list2-val)){if(tailNULL){headlist1;taillist1;}else{tail-nextlist1;taillist1;}list1list1-next;}else{if(tailNULL){headlist2;taillist2;}else{tail-nextlist2;taillist2;}list2list2-next;}}if(list1)tail-nextlist1;if(list2)tail-nextlist2;return head;
}有头单链表head-next指的是第一个节点的地址带头相当于开头多了一个节点但是节点里面的val不确定next指向下一个节点 无头单链表head指的是第一个节点的地址 OJ题默认不带头
代码二带头
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* head (struct ListNode*)malloc(sizeof(struct ListNode));//创建一个头struct ListNode* tail head;head-next NULL;//就是含有值的节点的第一个while (list1 list2){struct ListNode* next1 list1-next;struct ListNode* next2 list2-next;if ((list1-val) (list2-val)){tail-next list1;tail list1;list1 next1;}else{tail-next list2;tail list2;list2 next2;}}if (list1 ! NULL){tail-next list1;}if (list2 ! NULL){tail-next list2;}struct ListNode* list head-next;free(head);return list;
}思路每次取小的节点尾插到新的节点 注意mallloc的一个地址到最后要进行释放。 本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言小羊一定认真修改写出更好的文章~~
