每日一练（10）（删除链表的节点）每日一练（10）：删除链表的节

title: 每日一练（10）：删除链表的节点
categories:[剑指offer]
tags:[每日一练]
date: 2022/01/23
每日一练（10）：删除链表的节点给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 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 被删除的节点
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
方法一：常规解法（循环遍历）
如果头部的值是val直接返回头的next即可，不是遍历头部，找到val后直接跳过该节点，并返回head即可

ListNode* deleteNode(ListNode* head, int val) { if (head->val == val) { //头部的值是val直接返回头的next return head->next; } ListNode *node = head; while (node->next != nullptr) {//遍历 if (node->next->val == val) { node->next = node->next->next; return head; } node = node->next; } return head; }

方法二：递归
递归的方式就比较巧妙，可以理解从尾部到头判断，空则返回空，非空判断是否等于val，等于返回其next，不等于则返回本身

//递归1 ListNode* deleteNode(ListNode* head, int val) { if (head == nullptr) { return nullptr; }head->next = deleteNode(head->next, val); if (head->val == val) { return head->next; } return head; } //递归2 ListNode* deleteNode(ListNode* head, int val) { if (head == nullptr) { return nullptr; }head->next = deleteNode(head->next, val); //三目运算符 return head->val == val ? head->next : head; }

方法三：双指针
设置两个指针分别指向头节点，pre （要删除节点的前一节点）和 cur (当前节点)；
遍历整个链表，查找节点值为 val 的节点，找到了就删除该节点，否则继续查找。
1.找到，将当前节点的前驱节点（pre 节点或者说是之前最近一个值不等于 val 的节点）连接到当前节点（cur 节点）的下一个节点（pre->next = cur->next）。
【每日一练（10）（删除链表的节点）】2.没找到，继续遍历（cur = cur->next），更新最近一个值不等于 val 的节点（pre = cur）。

ListNode* deleteNode(ListNode* head, int val) { if(head == NULL) {//特判 return NULL; } if(head->val == val) {//头节点为要删除的节点 return head->next; }ListNode* cur = head; //当前节点 ListNode* pre = head; //保存删除节点的前一节点 while (cur != NULL && cur->val != val) { pre = cur; cur = cur->next; } if (cur != NULL) { pre->next = cur->next; }return head; }