算法刷题-链表-移除链表元素

链表操作中，可以使用原链表来直接进行删除操作，也可以设置一个虚拟头结点再进行删除操作，接下来看一看哪种方式更方便。

203.移除链表元素

力扣题目链接

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

思路

这里以链表 1 4 2 4 来举例，移除元素4。

203_链表删除元素1

如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点， 清理节点内存之后如图：

203_链表删除元素2

当然如果使用java ，python的话就不用手动管理内存了。

还要说明一下，就算使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。

这种情况下的移除操作，就是让节点next指针直接指向下下一个节点就可以了，

那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？

这里就涉及如下链表操作的两种方式：

  • 直接使用原来的链表来进行删除操作。
  • 设置一个虚拟头结点在进行删除操作。

来看第一种操作：直接使用原来的链表来进行移除。

203_链表删除元素3

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

203_链表删除元素4

依然别忘将原头结点从内存中删掉。
203_链表删除元素5

这样移除了一个头结点，是不是发现，在单链表中移除头结点 和 移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。

那么可不可以 以一种统一的逻辑来移除 链表的节点呢。

其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。

203_链表删除元素6

这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。

这样是不是就可以使用和移除链表其他节点的方式统一了呢？

来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。

最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点

C++代码

直接使用原来的链表来进行移除节点操作：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

设置一个虚拟头结点在进行移除节点操作：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

其他语言版本

C:
用原来的链表操作：

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* temp;
    // 当头结点存在并且头结点的值等于val时
    while(head && head->val == val) {
        temp = head;
        // 将新的头结点设置为head->next并删除原来的头结点
        head = head->next;
        free(temp);
    }

    struct ListNode *cur = head;
    // 当cur存在并且cur->next存在时
    // 此解法需要判断cur存在因为cur指向head。若head本身为NULL或者原链表中元素都为val的话，cur也会为NULL
    while(cur && (temp = cur->next)) {
        // 若cur->next的值等于val
        if(temp->val == val) {
            // 将cur->next设置为cur->next->next并删除cur->next
            cur->next = temp->next;
            free(temp);
        }
        // 若cur->next不等于val，则将cur后移一位
        else
            cur = cur->next;
    }

    // 返回头结点
    return head;
}

设置一个虚拟头结点：

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


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

Java：

/**
 * 添加虚节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}
/**
 * 不添加虚拟节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为null，提前退出
    if (head == null) {
        return head;
    }
    // 已确定当前head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}
/**
 * 不添加虚拟节点and pre Node方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val){
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null){
        while(curr.next!=null && curr.next.val == val){
            curr.next = curr.next.next;
        }
        curr = curr.next;
    }
    return head;
}

Python：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy_head = ListNode(next=head) #添加一个虚拟节点
        cur = dummy_head
        while(cur.next!=None):
            if(cur.next.val == val):
                cur.next = cur.next.next #删除cur.next节点
            else:
                cur = cur.next
        return dummy_head.next

Go：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := &ListNode{}
    dummyHead.Next = head
    cur := dummyHead
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummyHead.Next
}

javaScript:

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const ret = new ListNode(0, head);
    let cur = ret;
    while(cur.next) {
        if(cur.next.val === val) {
            cur.next =  cur.next.next;
            continue;
        }
        cur = cur.next;
    }
    return ret.next;
};

TypeScript:

版本一（在原链表上直接删除）：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function removeElements(head: ListNode | null, val: number): ListNode | null {
    // 删除头部节点
    while (head !== null && head.val === val) {
        head = head.next;
    }
    if (head === null) return head;
    let pre: ListNode = head, cur: ListNode | null = head.next;
    // 删除非头部节点
    while (cur) {
        if (cur.val === val) {
            pre.next = cur.next;
        } else {
            //此处不加类型断言时：编译器会认为pre类型为ListNode, pre.next类型为ListNode | null
            pre = pre.next as ListNode;
        }
        cur = cur.next;
    }
    return head;
};

版本二（虚拟头节点）：

function removeElements(head: ListNode | null, val: number): ListNode | null {
    // 添加虚拟节点
    const data = new ListNode(0, head);
    let pre = data, cur = data.next;
    while (cur) {
        if (cur.val === val) {
            pre.next = cur.next
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return data.next;
};

Swift：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    let dummyNode = ListNode()
    dummyNode.next = head
    var currentNode = dummyNode
    while let curNext = currentNode.next {
        if curNext.val == val {
            currentNode.next = curNext.next
        } else {
            currentNode = curNext
        }
    }
    return dummyNode.next
}

PHP:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 // 虚拟头+双指针
func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := &ListNode{}
    dummyHead.Next = head
    pred := dummyHead
    cur := head
    for cur != nil {
        if cur.Val == val {
            pred.Next = cur.Next
        } else {
            pred = cur
        }
        cur = cur.Next
    }
    return dummyHead.Next
}

RUST:

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
        let mut dummyHead = Box::new(ListNode::new(0));
        dummyHead.next = head;
        let mut cur = dummyHead.as_mut();
	// 使用take()替换std::men::replace(&mut node.next, None)达到相同的效果，并且更普遍易读
        while let Some(nxt) = cur.next.take() {
            if nxt.val == val {
                cur.next = nxt.next;
            } else {
                cur.next = Some(nxt);
                cur = cur.next.as_mut().unwrap();
            }
        }
        dummyHead.next
    }
}

Scala:

/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
  def removeElements(head: ListNode, `val`: Int): ListNode = {
    if (head == null) return head
    var dummy = new ListNode(-1, head) // 定义虚拟头节点
    var cur = head // cur 表示当前节点
    var pre = dummy // pre 表示cur前一个节点
    while (cur != null) {
      if (cur.x == `val`) {
        // 相等，就删除那么cur的前一个节点pre执行cur的下一个
        pre.next = cur.next
      } else {
        // 不相等，pre就等于当前cur节点
        pre = cur
      }
      // 向下迭代
      cur = cur.next
    }
    // 最终返回dummy的下一个，就是链表的头
    dummy.next
  }
}

Kotlin:

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        // 使用虚拟节点，令该节点指向head
        var dummyNode = ListNode(-1)
        dummyNode.next = head
        // 使用cur遍历链表各个节点
        var cur = dummyNode
        // 判断下个节点是否为空
        while (cur.next != null) {
            // 符合条件，移除节点
            if (cur.next.`val` == `val`) {
                cur.next = cur.next.next
            }
            // 不符合条件，遍历下一节点
            else {
                cur = cur.next
            }
        }
        // 注意：返回的不是虚拟节点
        return dummyNode.next
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/27569.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux下信号量使用总结

Linux下信号量使用总结

目录 1.Linux下信号量简介 2.POSIX信号量 2.1 无名信号量 2.2 有名信号量 3.System V信号量 1.Linux下信号量简介 信号量是解决进程之间的同步与互斥的IPC机制&#xff0c;互斥与同步关系存在的症结在于临界资源。 临界资源是在同一个时刻只容许有限个&#xff08;一般只有…
阅读更多...
【数据结构与算法】03 队列（顺序队列--循环队列--优先级队列--链队列）

【数据结构与算法】03 队列（顺序队列--循环队列--优先级队列--链队列）

一、概念1.1 队列的基本概念1.2 队列的顺序存储结构1.21 顺序队列&#xff08;静态队列&#xff09;1.22 循环队列1.23 优先级队列 1.3 队列的链式存储结构 二、C语言实现2.1 顺序存储2.11 顺序队列2.12 循环队列2.13 优先级队列 2.2 链式存储 一、概念 1.1 队列的基本概念 队…
阅读更多...
Linux内核中断和Linux内核定时器

Linux内核中断和Linux内核定时器

目录 Linux内核中断 Linux内核定时器 Linux内核中断 int request_irq(unsigned int irq, irq_handler_t handler, unsigned long flags,const char *name, void *dev) 功能&#xff1a;注册中断 参数&#xff1a; irq : 软中断号 gpio的软中断号 软中断号 gpio_to_i…
阅读更多...
【PCB专题】案例：绕等长怎么直接以颜色区分看出是否绕好

【PCB专题】案例：绕等长怎么直接以颜色区分看出是否绕好

PCB上对于时序的处理，在板卡上实际我们是通过绕等长的手段。做为一个合格的Layout工程师，等长的处理是不可或缺的技能。 一般来说，在绕等长的时候我们可以使用Delay Tune命令来改变走线的长度，然后通过规则管理器中分析看看哪根线长哪根线短。 但是在实际工作中，很可能绕着…
阅读更多...
Android应用程序进程的启动过程

Android应用程序进程的启动过程

Android应用程序进程的启动过程 导语 到这篇文章为止&#xff0c;我们已经简要地了解过了Android系统的启动流程了&#xff0c;其中比较重要的内容有Zygote进程的启动和SystemService以及Launcher的启动&#xff0c;接下来我们将要学习的是Android应用程序的启动过程&#xff…
阅读更多...
华为OD机试真题 JavaScript 实现【最多几个直角三角形】【2023Q1 100分】

华为OD机试真题 JavaScript 实现【最多几个直角三角形】【2023Q1 100分】

一、题目描述 有 N 条线段&#xff0c;长度分别为 a[1]-a[n]。 现要求你计算这 N 条线段最多可以组合成几个直角三角形&#xff0c;每条线段只能使用一次&#xff0c;每个三角形包含三条线段。 二、输入描述 第一行输入一个正整数 T (1< T< 100) &#xff0c;表示有…
阅读更多...
2023蓝桥杯大学A组C++决赛游记+个人题解

2023蓝桥杯大学A组C++决赛游记+个人题解

Day0 发烧了一晚上没睡着&#xff0c;感觉鼻子被打火机烧烤一样难受&#xff0c;心情烦躁 早上6点起来吃了个早饭&#xff0c;思考能力完全丧失了&#xff0c;开始看此花亭奇谭 看了六集&#xff0c;准备复习数据结构考试&#xff0c;然后秒睡 一睁眼就是下午2点了 挂了个…
阅读更多...
springboot项目外卖管理 day05-新增与删除套餐

springboot项目外卖管理 day05-新增与删除套餐

文章目录 一、新增菜品1.1、需求分析1.2、数据模型setmealsetmeal_dish 1.3、代码开发-梳理交互过程1.3.1、下拉框展示1.3.2、菜品窗口展示1.3.3、新增套餐 2、套餐分页查询 一、新增菜品 1.1、需求分析 套餐就是菜品的集合。 后台系统中可以管理套餐信息&#xff0c;通过新…
阅读更多...
一文打通：从字节码指令的角度解读前置后置自增自减（加加++减减--）

一文打通：从字节码指令的角度解读前置后置自增自减（加加++减减--）

文章目录 1.前置了解的知识1.1 栈这种数据结构1.2 局部变量表和操作数栈1.3 三个字节码指令 2.单独使用后置与前置2.1 后置字节码指令2.2 前置字节码指令2.3 总结 3.需要返回值的情况下使用后置与前置3.1 后置字节码指令3.2 前置字节码指令3.3 总结3.4 练习&#x1f340; 练习一…
阅读更多...
了解ASEMI代理英飞凌TLE6208-6G其功能和应用的综合指南

了解ASEMI代理英飞凌TLE6208-6G其功能和应用的综合指南

编辑-Z TLE6208-6G是一款高度集成、通用且高效的汽车半桥驱动器&#xff0c;由英飞凌设计。这种功能强大的设备专门设计用于满足汽车应用的苛刻要求&#xff0c;如控制直流电机、螺线管和电阻负载。在本文中&#xff0c;我们将深入研究TLE6208-6G的功能、优点和应用&#xff0…
阅读更多...
实现表白墙

实现表白墙

我们已经学习了Http以及Servlet类的相关知识 今天我们来实操一下,实现一个简单的既有前端又有后端的网站–表白墙 之前在学习前端的时候已经写过了表白墙的前端代码,存在两个问题 1.页面重启,数据丢失 2.数据只是在本地的,别人看不见 那么这样的问题我们要咋样解决呢? 引入…
阅读更多...
（七）CSharp-CSharp图解教程版-事件

（七）CSharp-CSharp图解教程版-事件

一、发布者和订阅者 发布者/订阅者模式&#xff08;publish/subscriber pattern&#xff09;&#xff1a; 很多程序都有一个共同的需求&#xff0c;即当一个特定的程序事件发生时&#xff0c;程序的其他部分可以得到该事件已经发生的通知。 发布者&#xff1a; 发布者类定义…
阅读更多...
Excel函数VLOOKUP常用方法

Excel函数VLOOKUP常用方法

一、基础用法 1、精确匹配 公式&#xff1a;VLOOKUP(待匹配值&#xff0c;查找范围&#xff0c;范围列数&#xff0c;查找方式) 定义好要输出表的表头和第一列&#xff0c;第一列即为要查找和匹配的父内容&#xff0c;在第二列输入公式&#xff0c;被查找表中一定也要将待查…
阅读更多...
基于SPAD / SiPM技术的激光雷达方案

基于SPAD / SiPM技术的激光雷达方案

激光雷达(LiDAR)是一种测距技术&#xff0c;近年来越来越多地用于汽车先进驾驶辅助系统(ADAS)、手势识别和3D映射等应用。尤其在汽车领域&#xff0c;随着传感器融合的趋势&#xff0c;LiDAR结合成像、超声波、毫米波雷达&#xff0c;互为补足&#xff0c;为汽车提供全方位感知…
阅读更多...
【力扣刷题 | 第六天】

【力扣刷题 | 第六天】

目录 前言&#xff1a; 344. 反转字符串 - 力扣&#xff08;LeetCode&#xff09; 541. 反转字符串 II - 力扣&#xff08;LeetCode&#xff09; 今天我们进入字符串章节的刷题旅程&#xff0c;希望各位小伙伴可以和我一起坚持下去&#xff0c;一起征服力扣&#xff01; 前言…
阅读更多...
前端前端学习不断

前端前端学习不断

卷吧卷吧...&#xff0c;这东西什么时候是个头啊……
阅读更多...
半导体器件基础（期末模电速成）

半导体器件基础（期末模电速成）

目录 1、半导体分类 2、PN结 3、二极管 4、稳压二极管 5、三极管 6、场效应管 1、半导体分类 2、PN结 3、二极管 伏安特性&#xff1a; 我们第七版模电书上给的正向导通压降分别约为0.7和0.2V&#xff0c;且硅的单向导电性更好 如何确定二极管状态&#xff1f; 阳极电压…
阅读更多...
怎么快速掌握Python爬虫技术？

怎么快速掌握Python爬虫技术？

Python总的来说是一门比较容易入门的编程语言&#xff0c;因为它的语法简洁易懂&#xff0c;而且有很多优秀的教程和资源可供学习。相比其他编程语言&#xff0c;Python 的学习曲线较为平缓&#xff0c;初学者可以很快上手&#xff0c;但要想深入掌握 Python&#xff0c;还需要…
阅读更多...
6款AI绘画生成器，让你的创作更有灵感

6款AI绘画生成器，让你的创作更有灵感

人工智能绘画听起来很高深&#xff0c;其原理是通过集成文本、图片和其他大数据数据来生成信息库&#xff0c;在输入文本描述的要求后&#xff0c;可以找到相应的视觉元素&#xff0c;然后拼凑起来生成符合文本描述的图片。 本文介绍非常好用的6款AI绘画生成工具 1.即时 AI 绘…
阅读更多...
location.href 和 document.URL 与 document.documentURI

location.href 和 document.URL 与 document.documentURI

location.href 和 document.URL 与 document.documentURI 相同点 获取到的值相同 不同点 location.hrefurl可以赋值, 效果类似location.assign(url) , 可以后退 document.URL 与 document.documentURI 是只读的, 赋值无效 location.href locationwindow.location true lo…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站