电子商务网站建设方案推荐,数据需求 网站建设,成都工程设计公司,win7 iis 添加网站#x1f680; 作者简介#xff1a;一名在后端领域学习#xff0c;并渴望能够学有所成的追梦人。 #x1f681; 个人主页#xff1a;不 良 #x1f525; 系列专栏#xff1a;#x1f6f8;剑指 Offer #x1f4d5; 学习格言#xff1a;博观而约取#xff0c;厚积而薄… 作者简介一名在后端领域学习并渴望能够学有所成的追梦人。 个人主页不 良 系列专栏剑指 Offer 学习格言博观而约取厚积而薄发 欢迎进来的小伙伴如果小伙伴们在学习的过程中发现有需要纠正的地方烦请指正希望能够与诸君一同成长 剑指 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.说明 题目保证链表中节点的值互不相同 若使用 C 或 C 语言你不需要 free 或 delete 被删除的节点 思路一 双指针法。因为题目中保证链表中节点的值互不相同所以我们可以通过比较链表中节点值是否和val相等来删除节点。 链表头节点为空的情况就不再细说直接返回nullptr 情况1.先判断头节点是否等于val如果等于val直接返回头节点的下一个节点即返回head-next 情况2.如果头节点不等于val则设置两个节点prev和cur分别记录上一个节点和当前节点如果cur节点的值等于val则让prev节点的next指针指向cur节点的下一个节点即prev-next cur - next 情况3.如果cur节点的值不等于val则通过prev cur;cur cur-next;继续向后遍历链表直至当cur为空。 代码如下
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {//判断头节点是否为空此步可以省略并不影响提交if(head nullptr)return nullptr;//当head-val等于val时返回head节点的下一个节点if(head-val val){head head-next;return head;}ListNode* cur head;//当前节点ListNode* prev head; //上一个节点while(cur){//当节点值等于val时让prev节点的next指针指向cur节点的下一个节点if(cur-val val){prev-next cur-next;//这里用break或者return head;都可以//return head;break;}//如果不相等则继续向后遍历prev cur;cur cur-next;}return head;}
};时间复杂度O(N) 空间复杂度O(1)
