【数据结构OJ题】移除链表元素

这篇具有很好参考价值的文章主要介绍了【数据结构OJ题】移除链表元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

移除链表元素


原题链接:力扣 

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

【数据结构OJ题】移除链表元素

 方法一:原地删除节点

思路:

 首先,定义两个指针:prve和cur。它们会在遍历链表的过程中分别指向当前节点的前一个节点和当前节点。初始情况下,prve指向NULL(因为当前节点是头结点),cur指向head。

【数据结构OJ题】移除链表元素

然后,我们使用while循环遍历链表,直到cur指向NULL(也就是遍历完整个链表)。在每个节点处,我们判断当前节点(cur)的值是否等于val。如果是,我们就需要将该节点从链表中移除。

如果当前节点cur是头结点,那么我们需要特殊处理,因为头结点没有前一个节点。此时,我们修改head指向cur的下一个节点,然后释放cur所指向的内存空间,使得cur指向新的头结点(即head),继续遍历整个链表。

如果当前节点cur不是头结点,那么我们需要将cur从链表中移除。此时,我们将prve的next指针指向cur的下一个节点,然后释放cur所指向的内存空间,使得cur指向prve的下一个节点(也就是新的当前节点),继续遍历整个链表。

如果当前节点cur的值不等于val,我们就只需要更新prve和cur的指向,使得它们分别指向当前节点的前一个节点和当前节点的下一个节点,然后继续遍历整个链表。

具体过程图解:

【数据结构OJ题】移除链表元素

 需要注意头节点的值是val的情况

代码:

struct ListNode* removeElements(struct ListNode* head, int val)
{
    //定义两个指针:prve和cur
    struct ListNode* prve = NULL;
    struct ListNode* cur = head;

    while (cur != NULL)
    {
        //判断当前节点(cur)的值是否等于val。如果是,我们就需要将该节点从链表中移除
        if (cur->val == val)
        {
            //如果当前节点cur是头结点,那么我们需要特殊处理
            if (cur == head)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                prve->next = cur->next;
                free(cur);
                cur = prve->next;
            }
        }
        //如果当前节点cur的值不等于val,我们就只需要更新prve和cur的指向
        else
        {
            prve = cur;
            cur = cur->next;
        }
    }
    return head;
}

方法二:遍历链表,把不是val的节点拿出来进行尾插到新链表

【数据结构OJ题】移除链表元素

下面有两种方式来实现;

不带哨兵卫头节点:

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

带哨兵卫头节点:

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

带哨兵卫头节点和不带哨兵卫头节点的方法类似。文章来源地址https://www.toymoban.com/news/detail-507860.html

到了这里,关于【数据结构OJ题】移除链表元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 单链表相关经典算法OJ题:移除链表元素

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 题目:移除链表元素 解法一: 解法一的代码实现: 解法二: 解法二代码的实现: 总结 世上有两种耀眼的光芒,一种是正在升起的太阳,一种是正在努力学习编程的你!一个爱学编程的人。各

    2024年02月04日
    浏览(48)
  • 数据结构c语言版:顺序表oj题练习(原地移除元素、合并两个有序数组)

    在单数组里面历遍找val,如果是val,就删除。不是就跳过。 时间复杂度O(n^2),最坏情况每个都是val。相当于一个等差数列。 比如 下标0开始找,0不是,不动数组 下标1,1不是,不动数组 下标2,2是,删除元素,变成【0,1,2,3,0,4,2】 下标2,2是,删除元素,变成【0,

    2024年01月23日
    浏览(66)
  • 移除链表元素详解

      原题出处: . - 力扣(LeetCode) 我们可以新创建一个链表,然后将不等于val的节点拿下来进行尾插,这样的方式更加简易,只需要遍历整个链表即可。 我们首先使用一个指针cur来遍历原链表,来获取不等于val的节点。 如果cur的next等于val就跳过这个节点,如果不等于val就尾

    2024年04月26日
    浏览(43)
  • 移除链表元素

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:leetcode练习题 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 题目链接: 移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你 删除链表中所有满足 Node.val == val 的节点 , 并返

    2024年02月04日
    浏览(42)
  • 203.移除链表元素

    循环遍历整个链表 定义两个指针:prev,cur 如果cur是要删除的节点,prev-cur-next,然后free(cur) 但是注意每次都要新定义一个节点del,用来free,不影响原来的cur节点往下循环 更新cur和prev 但是需要注意如果删除的是头节点,就要特殊处理,画图带上指针,情况分析,一目了然。

    2024年01月22日
    浏览(44)
  • 算法刷题-链表-移除链表元素

    链表操作中,可以使用原链表来直接进行删除操作,也可以设置一个虚拟头结点再进行删除操作,接下来看一看哪种方式更方便。 力扣题目链接 题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [],

    2024年02月08日
    浏览(51)
  • Java移除链表元素

    目录 1.题目描述 2.题解 题解1 题解2 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足  Node.val == val  的节点,并返回  新的头节点  。 示例 输入:head = [1,2,6,3,4,5,6],val = 6 输出:[1,2,3,4,5] 输入:head = [], val = 1 输出:[] 输入:head = [7,7,7,7], val = 7 输出:

    2024年02月07日
    浏览(33)
  • 移除链表元素 , 设计链表 ,反转链表

    leetcode 删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 移除元素  主要是  找到要移除的前一个  , 之后才能移除 。采用虚拟头节点的方法

    2024年02月08日
    浏览(44)
  • leetcode203. 移除链表元素

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【LeetCode】 🍓希望我们一起努力、成长,共同进步。 题目链接 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的

    2024年02月06日
    浏览(39)
  • LEEDCODE 203移除链表元素

    2024年02月06日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包