教育集团网站设计策划书,网站建设的总结,无锡网站建设专注千客云网络,wordpress插件汉化下载地址如果您是第一次看我写的博客#xff0c;可以给我点个赞并关注我吗#xff0c;我会持续分享更多有意思的干货。 每日一题系列从今天开始#xff0c;由于我是个算法小白#xff0c;所以我会给你看看小白是怎么学的。#x1f487; 文章目录1 题目2 思路3 代码4 小结1 题目
剑… 如果您是第一次看我写的博客可以给我点个赞并关注我吗我会持续分享更多有意思的干货。 每日一题系列从今天开始由于我是个算法小白所以我会给你看看小白是怎么学的。 文章目录1 题目2 思路3 代码4 小结1 题目
剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值定义一个函数删除该节点。
返回删除后的链表的头节点。
注意此题对比原题有改动 示例 1: 输入: head [4,5,1,9], val 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点那么在调用了你的函数之后该链表应变为 4 - 1 - 9. 示例 2: 输入: head [4,5,1,9], val 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点那么在调用了你的函数之后该链表应变为 4 - 5 - 9. 输入: head [4,5,1,9], val 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点那么在调用了你的函数之后该链表应变为 4 - 5 - 9.
说明
题目保证链表中节点的值互不相同 若使用 C 或 C 语言你不需要 free 或 delete 被删除的节点
2 思路
一开始没看清题意我以为是有头结点的所以导致我用示例编译的时候是对的提交上去是错的。
首先我是这么想的先用一根指针来寻找要删除结点的前置结点找到后再用一根指针指向要删除的结点最后改变指针走向释放即可。
但是还需要考虑删除的是首元节点的情况如果是首元节点那么返回的就不会是头指针而是头指针的下一个结点了为此我们要提前判断该情况。
用一幅图来表明如下 至于删除最后一个结点也不用担心因为如果删除最后一个结点那么如图所示p-next会指向空这正是我们需要的。
3 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {//删除首元节点ListNode *p head; if(head-val val)return head-next;//普通情况while(p-next-val ! val)p p-next;ListNode * q p-next;p-next q-next;return head;}
};4 小结
这个算法的最好时间复杂度是O(1)最坏时间复杂度是O(n)。 好了这道题实际上非常简单但是我刚入门嘛比较菜这里算法我觉得还有个不好的一点是忘记判断val的存在性了。如果有什么疑问可以在评论区告诉我哦