剑指 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 被删除的节点
解题思路
结构图大体如下
我们假设储存的四个值是 4 5 1 9
要删除的值是 5
我们大概来看一下思路
这里我们可以发现 我们找到要删除的值的时候
这个时候我们需要做三件事
第一 将前面的next指向被删除下面一个结构体的指针
第二 释放cur的位置
第三 cur前面的位置指向下面一个结构体的位置
那么如果说像现在的这种情况 后面没有要删除的值了 就可以一直cur指向下一个位置
那么我们想想看 指向什么位置才可以结束呢？
我们可以发现 当cur指向空的时候 循环条件就可以结束了
当然 这里有一个
特殊情况
就是如果说 第一个值就是我们要找的值
这个时候pre指向的还是空指针
这里我们就要用到头删
这个时候我们只需要用头删就可以了
代码源码
代码源码表示如下
struct ListNode* deleteNode(struct ListNode* head, int val) { // 创建需要用到的指针 struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode)); pre = NULL; cur = head; // 还有一种特殊情况 那就是当头就是要找的值的时候 下面的代码就不适用了 所以说我们这里要添加一个特殊情况 头部就是要找的值 // 按照一般情形的代码 while (cur != NULL) { while (head->val == val) { cur = head; head = head->next; free(cur); cur = head; } if (cur->val != val) { pre = cur; cur = cur->next; } else { pre->next = cur->next; free(cur); cur = pre->next; } } //但是上面的代码只能循环一次 想要删除掉所有的数 我们只需要在上面添加一个条件 return head; }
