素材网站 源码,上海专业建设网站制作,wordpress 4.9 中文版,潜江公司做网站目录 前言1.移除元素1.1 链表1.2 数组 2.双指针2.1 找链表的中间结点2.2 找倒数第k个结点 总结 前言
解代码题 先整体#xff1a;首先数据结构链表的题一定要多画图#xff0c;捋清问题的解决思路#xff1b; 后局部#xff1a;接着考虑每一步具体如何实现#xff0c;框架… 目录 前言1.移除元素1.1 链表1.2 数组 2.双指针2.1 找链表的中间结点2.2 找倒数第k个结点 总结 前言
解代码题 先整体首先数据结构链表的题一定要多画图捋清问题的解决思路 后局部接着考虑每一步具体如何实现框架搭好后处理坑点考虑细枝末节通常要考虑以下几个容易出错的点
需要单独处理的头结点、尾结点越界问题头指针为NULL循环继续、结束条件等
而思路这一块有的思路好想但是无论从时间复杂度还是空间复杂度上来看可能不是优良的算法。但有一些比较清奇的思路见得题多了反思总结也就收入囊中啦比如下面介绍的双指针以及翻转数组的思路都很优秀。
每个小节开头蓝色字体是题目链接大家可以先做一下题~ 1.移除元素
1.1 链表
203.移除链表元素题目链接 思路1遍历链表删除数据域为val的结点 思路2将值不为val的节点尾插到新的链表中返回新链表的头结点头指针。
注意两种思路整体都是遍历原链表但是有几个坑
坑点1如果尾插第一个结点要更改新的头指针newhead但后续插入不需要再更改头指针。坑点2如果最后一个结点的值不是val那么将其尾插到新链表其next指针域为NULL但是如果最后一个结点的值是val其前一个结点假设prev指向该结点被尾插到新链表prev-next指向的最后一个节点数据域为val被free那么prev-next是野指针所以要将其置为NULL.
比如下图中当数据域为5的结点被尾插到新链表之后tail指向该节点tail-nextp但是free§之后p就是野指针了应将tail-next手动置为NULL.
坑点3第二点和链表本身为空可以合在一起考虑如果head为NULL那么cur为NULL遍历原链表的while循环不会执行tail为NULLnewhead为NULL直接返回即可而如果tail不为NULLtail-next有可能为NULL不考虑太多直接置为NULL.
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* curhead, *newheadNULL, *tailNULL;//cur用于遍历要删除的链表//newhead用于存放要新链表的头指针用于返回//tail用于尾插否则每次尾插都要遍历新链表找尾节点效率不高while(cur)//while循环遍历要删除的链表{//结点数据域为val与非val分开处理val则删除非val则尾插到新链表if(cur-val!val){//插入第一个元素和后续元素不同的是插入第一个元素需要更改头指针要单独处理//坑点1 if(tailNULL)newheadtailcur;else{tail-nextcur;tailtail-next;}curcur-next;}else{struct ListNode* nextcur-next;free(cur);curnext;}}//坑点2,3if(tail)tail-nextNULL;return newhead;
}1.2 数组
27.移除元素题目链接 这个题的思路可以是创建一个新的数组存储值不为val的数组元素。 也可以使用双指针数组的指针就是下标使用src指针遍历数组如果值不为val就将其赋值到nums[dst].
int removeElement(int* nums, int numsSize, int val) {int src0,dst0;while(srcnumsSize){if(nums[src]!val)nums[dst]nums[src];//只有当值非val的时候存储到数组中以dst为指针也就是舍弃值为val的元素elsesrc;//每次循环src都达到遍历数组的目的}return dst;
}2.双指针
2.1 找链表的中间结点
876.链表的中间结点题目链接 考虑快慢指针fast, slow指针刚开始均指向第一个结点接着fast每次走两步slow每次走一步如果是奇数结点fast-next为NULL时slow指向中间结点如果是偶数结点fast为NULL时slow指向两个中间结点的第二个结点。也即fast遍历链表当fast为NULL或fast-next为NULL时停止循环返回slow.
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fasthead,*slowhead;while(fast fast-next){fastfast-next-next;slowslow-next;}return slow;
}这个思路和下面这道题有点像
2.2 找倒数第k个结点
02.返回倒数第k个节点题目链接 思路考虑双指针fast走到NULL终止循环那么此时fast相当于倒数第0个结点slow是倒数第k个结点也即fast比slow多走了k步那么让fast先走k步接着fast和slow同步往前走直到fast为NULL. 代码如下 如果fast走到最后一个节点停止那么考虑fast先走k-1步
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
int kthToLast(struct ListNode* head, int k){struct ListNode* fasthead,*slowhead;while(k--){if(fastNULL)return NULL;//考虑链表本身为空的情况fastfast-next;}while(fast){fastfast-next;slowslow-next;}return slow-val;
}总结
链表代码题考虑时间复杂度、空间复杂度同时要多见题多见经典题多练总结经典思路以及常见坑点写代码时考虑细枝末节。细节考虑不到位可能存在提交不通过对未通过测试用例的提示进行分析调试提升自身解决问题的能力。
