首页 > 其他分享 >lc203.移除链表元素

lc203.移除链表元素

时间:2023-03-11 13:48:14浏览次数:40  
标签:结点 cur val head next 链表 移除 lc203

题目

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

示例
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

代码

  • 使用的是while而不是if,因为移除结点是一个持续的过程,直到遍历所有结点才会结束
  • cur -> next -> val作为判断的结点的原因:删除一个结点时要找上一个结点和下一个结点,如果cur指向了val结点,单向链表中找不到上一个结点了,所以要通过cur -> next来找等于val的结点
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //头结点对应目标值,删除头结点
		//头结点不能等于NULL,否则操作空指针就会报错
        while( head != NULL && head -> val == val){ //头结点的数值域等于val
            ListNode * temp = head; //创建一个temp,后续释放原head内存
            head = head -> next;    //将下一个节点作为头结点
            delete temp;    //释放原结点
        }

        //非头结点
        ListNode* cur = head;   // 定义一个临时指针指向头结点
		//指向头结点的原因:删除一个结点时要找上一个结点和下一个结点,如果cur指向了val结点,单向链表中找不到上一个结点了,所以要通过cur -> next来找等于val的结点
        //链表中最后一个结点怎么检查,cur -> next = NULL时,怎么进入进入循环执行if语句检查   每次检查的都是cur的下一个结点,当cur++时,此结点已经经过了检查,是可以保留的结点
        while(cur != NULL && cur -> next != NULL){  //头结点本身和指向的结点不为空
            if(cur -> next -> val == val){ //头结点指向的结点值等于val,有满足条件的结点存在
                ListNode* temp =cur -> next; //将后续要释放的内存赋值给中间变量
                cur -> next = cur -> next -> next; //从链表中删除满足条件的结点
                delete temp;    //释放满足条件的结点
            }
            else
                cur = cur -> next;  //累加,遍历整个链表
        }

        return head;    //返回删除后的链表

    }
};

虚拟头结点的方法

  • return 的是hummyHead -> next,原来的head可能已经被删除了
 //虚拟一个头结点,使得原来的头结点的操作和其余结点相同
        ListNode* dummyHead = new ListNode(0);
        dummyHead -> next = head;   //设置的虚拟结点指向头结点
        ListNode* cur = dummyHead; //创建一个用于遍历链表的临时指针
        while(cur -> next != NULL) {
            if(cur -> next -> val == val){
                ListNode* temp = cur -> next;
                cur -> next = cur -> next -> next;
                delete temp;
            }
            else
                cur = cur -> next;
        }
        head = dummyHead -> next;   //没有这行会出错,没有这行head可能为空指针(原head可能已经被删了)
        delete dummyHead;    //释放创建的虚拟结点
        return head;

标签:结点,cur,val,head,next,链表,移除,lc203
From: https://www.cnblogs.com/wangshoutong/p/17205658.html

相关文章

  • 数组模拟链表
    单链表数组模拟链表比动态链表效率更高。\(head\)作为指向头结点的指针,\(idx\)作为当前结点索引,每次执行完操作都要idx++;数组\(e[]\)用来保存当前结点的值,\(ne[......
  • 单链表经典面试题
    单链表经典面试题1.求单链表中有效节点的个数思路:直接遍历节点个数即可,如果带头节点则不统计头节点方法代码:/***遍历求链表有效节点个数,但不统计头节点*@param......
  • Leetcode24. 两两交换链表中的节点
    题目描述:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 思路:使用虚拟头结点,这样会......
  • LeetCode206. 反转链表
    题目描述:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。示例1:输入:head=[1,2,3,4,5]输出:[5,4,3,2,1]示例2:输入:head=[1,2]输出:[2,1]......
  • Leetcode707. 设计链表
    题目描述:设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果......
  • leetcode203. 移除链表元素
    题目描述:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val==val 的节点,并返回 新的头节点 。示例1:输入:head=[1,2,6,3,4,5,6],......
  • [chatGPT]unity中,我希望一个角色有一个链表能获取到场上所有“creature”的transform,
    关键字:unity游戏对象管理,unity,unity实例管理,unity触发方法我unity中,我希望一个角色有一个链表能获取到场上所有“creature”的transform,当creature增加或减少时刷新这个......
  • 【数据结构入门】单链表(SList)详解(增、删、查、改)
    1、链表的概念及结构1.1链表的概念概念:链表是一种物理存储结构上非连续、非顺序的存储结构,但链表在逻辑上是连续的,顺序的,而数据元素的逻辑顺序是通过链表中的指针连接次序实......
  • 剑指 Offer 18.删除链表节点
    题目表述   解法双指针法classSolution{public:ListNode*deleteNode(ListNode*head,intval){ListNode*a=head->next;......
  • 单向环形链表应用场景
    约瑟夫问题  思路:  ......