首页 > 其他分享 >[Leetcode]删除链表中等于val 的所有结点

[Leetcode]删除链表中等于val 的所有结点

时间：2023-04-17 22:31:55浏览次数：116  
标签：ListNode cur val next 链表 tail Leetcode struct

力扣链接

[Leetcode]删除链表中等于val 的所有结点_结点

方法一:

使用前后两个指针,cur指向当前位置,prev指向前一个位置,通过改变指向和释放结点来删除val

[Leetcode]删除链表中等于val 的所有结点_野指针_02

初步代码,还存在问题:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val != val)
        {
            prev = cur;
            cur = cur->next;

        }
        else
        {
           
            prev->next = cur->next;
            free(cur);
           // cur = cur->next;//错误,cur已经被释放,野指针
            cur = prev->next;
        }
    }
    return head;


}

[Leetcode]删除链表中等于val 的所有结点_链表_03

null pointer出现了空指针

通过测试用例代码走读分析问题:

[Leetcode]删除链表中等于val 的所有结点_野指针_04

如果第一个就是要删的值,也就是头删,会出现问题

所以这种情况要单独处理

最终代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        else
        {
            if(prev == NULL)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                prev->next = cur->next;
            free(cur);
            //cur = cur->next;//和下一句等价,但是cur已经释放,这句会出现野指针
            cur = prev->next;
            }
        
        }


    }


    return head;//返回一个新的头,不需要用二级指针


}

方法二:

把不是val的值尾插到新链表

[Leetcode]删除链表中等于val 的所有结点_野指针_05

[Leetcode]删除链表中等于val 的所有结点_链表_06

初步代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



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;


        }
    }
    return newHead;
}

[Leetcode]删除链表中等于val 的所有结点_链表_07

通过走读代码我们发现,当最后一个结点的值为val时,释放节点后前面尾插的结点仍然指向最后一个结点,这里只需要将tail->next置空即可,修改后代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



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;


        }
    }
    tail->next = NULL;
    return newHead;
}

但是代码仍然存在错误,运行如下:

[Leetcode]删除链表中等于val 的所有结点_链表_08

显而易见,需要考虑链表为空的情况

改进后代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



struct ListNode* removeElements(struct ListNode* head, int val)
{
    if(head== NULL)
    {
        return NULL;
    }
    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;


        }
    }
    tail->next = NULL;
    return newHead;
}

报错:

[Leetcode]删除链表中等于val 的所有结点_结点_09

这时代码直接指向最后一个else,此时tail为空,tail->next不合理,所以干脆前面不进行判断,而在后面对tail进行判断

最终代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */



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;
}

标签：ListNode,cur,val,next,链表,tail,Leetcode,struct
From： https://blog.51cto.com/u_15992140/6196392

相关文章

  • 4月17日leetcode二叉树的层序遍历II
    给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）(出自力扣）这个昨天的二叉树的层序遍历有所不同：需要将从后往前层序遍历二叉树，其实很简单，只需要用vector的逆置函数，将vector中的vector逆置即可。这里顺便......
  • LeetCode Top100: 二叉树的最大深度 （python）
     给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 [3,9,20,null,null,15,7]，3/\920/\157返回它的最大深度 3。 以下是Python代码实现：cl......
  • 4月16日leetcode二叉树前序遍历创建字符串，二叉树的层序遍历
    给你二叉树的根节点root，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。空节点使用一对空括号对"()"表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。来源：力扣（LeetCode）链接：https://leetcode.cn/pro......
  • LeetCode Top100：二叉树的中序遍历（Python）
     给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。 示例1：输入：root=[1,null,2,3]输出：[1,3,2]示例2：输入：root=[]输出：[]示例3：输入：root=[1]输出：[1] 提示：树中节点数目在范围 [0,100] 内-100<=Node.val<=100 以下是一个Python程序，......
  • #yyds干货盘点# LeetCode程序员面试金典：找出字符串中第一个匹配项的下标
    题目：给你两个字符串 haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从0开始）。如果 needle不是haystack的一部分，则返回 -1。 示例1：输入：haystack="sadbutsad",needle="sad"输出：0解释："sad"在下标0和6处匹配。第一个匹......
  • #yyds干货盘点# LeetCode面试题：单词搜索
    1.简述：给定一个 mxn二维字符网格 board和一个字符串单词 word。如果 word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示......
  • 2-211-(LeetCode-470) 用 Rand7() 实现 Rand10()
     1.题目 https://leetcode.cn/problems/implement-rand10-using-rand7/submissions/425373186/ 2.解法 classSolutionextendsSolBase{publicintrand10(){inttemp=40;while(temp>=40){temp=(rand7()-1)*7......
  • org.apache.ibatis.binding.BindingException: Invalid bound statement (not found)
    1.问题org.apache.ibatis.binding.BindingException:Invalidboundstatement(notfound)Springboot项目中，在mybatis中mapper数据库操作接口(有的称DAO，有的直接说mapper,都只同一文件)与mapper配置文件在做映射绑定的时候出现问题，简单说，就是接口与xml要么是找不到，要么是找到了......
  • 2-209-(LeetCode-121) 买卖股票的最佳时机
     1.题目 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/121. 买卖股票的最佳时机 2.解法2.1解法一：动态规划  2.2解法二：非动态规划 if(prices.length<2){return0;}intmin=prices[0];......
  • 2-207-通过（LeetCode-509）熟悉动态规划的解题步骤
    1.题目 运态规划的定义   动态规划的解题步骤  2.解法2.1递归 publicstaticintfibonacci(intn){if(n==0){return0;}if(n==1){return1;}returnfibonacci(n-1)+fibonacci(n-2);}2.2运态规划+递归......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99