删除链表的节点

简介: 删除链表的节点

剑指 Offer 18. 删除链表的节点

  给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

这是leetcode上的一个题

示例 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.

解题思路

结构图大体如下

我们可以定义一个新链表newHead来存储与val不同的值 ,将与val值不同的节点尾插到新链表,但是没次尾插一个节点都需要找尾,我们再定义一个tail指针来帮助我们尾插,这样就简单很多了。

我们假设储存的四个值是 4 5 1 9

要删除的值是 1

我们大概来看一下思路

这里我们可以发现 我们找到要删除的值的时候

这个时候我们需要做三件事

第一 将前面的next指向被删除下面一个结构体的指针

第二 释放cur的位置

第三 cur前面的位置指向下面一个结构体的位置

那么如果说像现在的这种情况 后面没有要删除的值了 就可以一直cur指向下一个位置

那么我们想想看 指向什么位置才可以结束呢?

我们可以发现 当cur指向空的时候 循环条件就可以结束了

当然 这里有一个特殊情况

就是如果说 第一个值就是我们要找的值

这个时候pre指向的还是空指针

这里我们就要用到头删


这里我们还需要定义一个del来表示cur的下一个位置,防止我们释放cur的时候出现野指针问题

直接看代码:

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* newHead = NULL, * tail = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val != val)
        {
            if (tail == NULL)
            {
                newHead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    if (tail)
        tail->next = NULL;
    return newHead;
}

这里还有一个问题,当最后一个节点是与val相同的值,释放掉以后tail指向也会出现野指针的问题,所以我们加上这句判断


 if (tail)
 tail->next = NULL;


整个代码就完整了,不会出现错误了

以上便是本文所有内容,如有错误请各位大佬不吝赐教,感谢留言

目录
相关文章
|
3月前
|
机器学习/深度学习 算法
24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交
1. **两两交换链表中的节点**:通过引入虚拟头结点,使所有节点都能采用统一的交换逻辑,避免对头结点单独处理。 2. **删除链表的倒数第N个节点**:利用双指针技巧,让快慢指针保持N个节点的距离,当快指针到达末尾时,慢指针正好指向待删除节点的前一个节点。 3. **链表相交**:先计算两链表长度并调整起点,确保从相同距离末尾的位置开始遍历,从而高效找到相交节点或确定无交点。 以上方法均在时间复杂度和空间复杂度上进行了优化,适合用于理解和掌握链表的基本操作及常见算法设计思路。
|
存储 Python
链表中插入节点
链表中插入节点
|
11月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
121 0
LeetCode第二十四题(两两交换链表中的节点)
|
11月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
121 0
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
12月前
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
|
11月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
126 0
|
12月前
04_两两交换链表中的节点
04_两两交换链表中的节点
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
145 5
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
132 4