首页 > 其他分享 >【LeetCode链表#6】移除链表元素

【LeetCode链表#6】移除链表元素

时间:2023-01-12 21:22:57浏览次数:83  
标签:head ListNode cur val LeetCode 链表 移除 next 节点

移除链表元素

题目

力扣题目链接(opens new window)

题意:删除链表中等于给定值 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
输出:[]

初见思路

就操作链表咯

常规思路

如果直接使用头节点作为当前节点的话,在删除头节点时的操作会与删除其他节点时不一致

要统一所有节点的删除方式,需要引入虚拟节点dummy

这样,每当需要删除某个节点时(包括头节点)

都可以遵循:将待删除节点的前一个节点的next指针指向待删除节点的后一个节点 这样一个规则

203_链表删除元素6

解题模板

不使用虚拟节点

具体还有两种写法:使用pre、cur指针和只用cur指针

具体看代码:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //删除头节点的情况
        while(head != null && head.val == val){
            head = head.next;
        }
        //不要忘了,如果头节点为空就直接退出
        if(head == null){
            return head;
        }

        //删除其他节点的情况
        //正常情况
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null){
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }



        // //只使用一个临时节点cur
        // //当前节点的指针应该指向head而不是head.next
        // //因为如果要删除的就是当前cur指向的值,那么直接指向head的方式就有问题,因为在单向链表中,它找不到待删除节点的上一个节点
        // //而第二种方式就避免了这种情况
        // ListNode cur = head;
        
        // while(cur != null){
        //     while(cur.next != null && cur.next.val == val){
        //         cur.next = cur.next.next;
        //     }
        //     cur = cur.next;
        // }
        

        return head;//不是返回临时节点cur,要找回最开始的头节点head
    }
}
使用虚拟节点
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){//先判断头节点是否为空,防止操作空指针
            return head;
        }
        //创建一个虚拟节点
        ListNode dummy = new ListNode(1, head);
        //定义前一个节点pre与当前节点cur
        ListNode pre = dummy;
        ListNode cur = head;
        while(cur != null){//要用循环而不是if,因为删除操作应该是连续的
            if(cur.val == val){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        //注意!要返回虚拟节点的下一个节点,即头节点。而不是直接返回头节点,因为原来的head有可能已经被删了
        return dummy.next;
    }
}

反正以后就记住使用虚拟节点的方式就行,用的时候也优先这种方式

标签:head,ListNode,cur,val,LeetCode,链表,移除,next,节点
From: https://www.cnblogs.com/DAYceng/p/17047947.html

相关文章

  • Windows 发布新年首次Dev频道更新:移除广告和WS
    据XDA论坛消息,微软Windows团队在假期休假几日后,目前已重启开发工作。近日发布了Dev版本25272。此次更新没有带来新功能,主要是移除以往不受欢迎的功能。其中一个功能是搜......
  • leetcode-easy-两数之和
    两数之和一解题思路:使用循环的方法从前到后计算给出的数组,直到找到目标题目#给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target......
  • 块状链表详解
    引入块状链表,顾名思义,就是把分块和链表结合起来的神奇数据结构。分块区间操作复杂度优秀,但是不能支持插入/删除操作。链表单点插入删除复杂度优秀,但是不能支持大......
  • LeetCode刷题(13)~移动零
    题目描述给定一个数组nums,编写一个函数将所有0移动到数组的末尾,同时保持非零元素的相对顺序。示例:输入:[0,1,0,3,12]输出:[1,3,12,0,0]说明:必须在原数组上操作,不能拷......
  • LeetCode刷题(12)~加一
    题目描述给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位,数组中每个元素只存储单个数字。你可以假设除了整数0之外,这个整......
  • LeetCode刷题(10)~只出现一次的数字
    题目描述给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。说明:你的算法应该具有线性时间复杂度。你可以不使用额外......
  • LeetCode刷题(11)~ 两个数组的交集 II
    题目描述给定两个数组,编写一个函数来计算它们的交集。示例1:输入:nums1=[1,2,2,1],nums2=[2,2]输出:[2,2]示例2:输入:nums1=[4,9,5],nums2=[9,4,9,8,4]输出:[4,9]......
  • LeetCode刷题(9)~存在重复元素
    题目描述给定一个整数数组,判断是否存在重复元素。如果任意一值在数组中出现至少两次,函数返回true。如果数组中每个元素都不相同,则返回false。示例1:输入:[1,2,3,1]输......
  • LeetCode刷题(8)~旋转数组
    题目描述给定一个数组,将数组中的元素向右移动k个位置,其中k是非负数。示例1:输入:[1,2,3,4,5,6,7]和k=3输出:[5,6,7,1,2,3,4]解释:向右旋转1步:[7,1,2,3,4,5,6......
  • LeetCode刷题(7)~删除排序数组中的重复项
    题目描述给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用......