leetcode203-----移除链表元素

news/2025/2/28 15:52:03/

目录

一、题目简介

二、解题思路

三、代码

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

1. 时间复杂度

删除头节点：

删除非头节点：

综合分析：

2. 空间复杂度

总结：

3.2 设置虚拟头节点

时间复杂度：

空间复杂度：

结论：

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

一、题目简介

题目链接：203. 移除链表元素 - 力扣（LeetCode）

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

输入：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
输出：[]提示：
  • 列表中的节点数目在范围 [0, 10^4] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

二、解题思路

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

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

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

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

建议删除之后的节点要及时清理该节点所占用的内存，如果不及时清理，会引发内存泄漏问题：

内存泄漏的定义：内存泄漏（Memory Leak）是指在程序运行过程中，程序没有及时释放已经不再使用的内存资源，导致这些资源无法被操作系统回收，从而导致系统的可用内存逐渐减少，最终可能导致程序或系统崩溃。

这种情况下的移除操作，就是让节点next指针直接指向下下一个节点就可以了，那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表中的第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？

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

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

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

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

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

 依然别忘将原头结点从内存中删掉。

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

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

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

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

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

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

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

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

三、代码

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

#include<iostream>
// 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。struct ListNode
{int data; // 定义节点数据域ListNode* next; // 定义节点指针域ListNode(int x) :data(x),next(nullptr){} // 节点的构造函数
};ListNode* removeElements(ListNode* head, int val){// 删除头节点//这段代码的目标是删除链表中所有值为 val 的连续头节点。每次删除一个节点后，头指针 head 被更新为下一个节点，直到找到一个节点的值不等于 val。while(head!=nullptr && head->data==val){ // 注意这里不能是 ifListNode* tmp = head; // 创建一个指向当前头节点的指针head = head->next; // 更新head指针，指向当前节点的下一个节点，即将链表的头节点向后移动delete tmp; // 释放掉删掉的节点的内存，避免内存泄漏}// 删除非头节点ListNode* ptr1 = head; // 定义链表遍历指针while(ptr1->next!=nullptr && ptr1!=nullptr){ // 遍历整个链表if(ptr1->next->data==val){ListNode* tmp = ptr1->next;ptr1->next = ptr1->next->next;delete tmp; // 释放掉被删除节点所占用的内存，避免内存泄漏}else{ // 不写 else ，即在这里只写 ptr1=ptr1->next;，程序运行会面临崩溃ptr1=ptr1->next;}  }return head;
}int main(){// 定义一个新链表 1--2--6--2ListNode* L_head = new ListNode(1); // 新链表的头节点为L_headL_head->next = new ListNode(2);L_head->next->next = new ListNode(6);L_head->next->next->next = new ListNode(2);int val=2; // 定义要删除的元素ListNode* new_head = removeElements(L_head,val);return 0;
}

对上述代码进行分析：

一、删除头节点需单独处理 

// 删除头节点//这段代码的目标是删除链表中所有值为 val 的连续头节点。每次删除一个节点后，头指针 head 被更新为下一个节点，直到找到一个节点的值不等于 val。while(head!=nullptr && head->data==val){ // 注意这里不能是 ifListNode* tmp = head; // 创建一个指向当前头节点的指针head = head->next; // 更新head指针，指向当前节点的下一个节点，即将链表的头节点向后移动delete tmp; // 释放掉删掉的节点的内存，避免内存泄漏}

子代码第一行：必须使用while循环而不能使用if判断语句，原因如下：

假设有一个链表，元素为 1 -> 1 -> 1 -> 2 -> 3，我们需要删除所有值为 1 的节点。如果我们使用 if 语句，那么当删除第一个值为 1 的节点后，程序会跳出 if 语句，导致后续值为 1 的节点无法被继续删除。因为 if 语句只会在条件满足时执行一次，删除一个节点后就停止了对后续节点的检查。

而使用 while 循环可以确保在删除当前节点后，循环会继续判断下一个节点是否符合条件，从而能够连续删除所有值为 1 的节点。通过 while 循环，直到没有更多的值为 1 的节点为止，才能确保所有目标节点都被删除。

 二、删除非头节点的逻辑

正确形式的代码如下，记为A。 

// 正确形式A
// 删除非头节点ListNode* ptr1 = head; // 定义链表遍历指针while(ptr1->next!=nullptr && ptr1!=nullptr){ // 遍历整个链表if(ptr1->next->data==val){ListNode* tmp = ptr1->next;ptr1->next = ptr1->next->next;delete tmp; // 释放掉被删除节点所占用的内存，避免内存泄漏}else{ // 不写 else ，即在这里只写 ptr1=ptr1->next;，程序运行会面临崩溃ptr1=ptr1->next;}  }

为什么while循环判断条件是 (ptr1->next!=nullptr && ptr1!=nullptr)，单向链表在删除节点时，必须要找到被删除节点的前一个节点，因此我们用ptr1记录被删除节点的前一个节点，而ptr1->next表示被删除的节点。

上述代码中else必须存在，不能写成如下形式，错误形式的代码记为B：

// 错误形式B
// 删除非头节点ListNode* ptr1 = head; // 定义链表遍历指针while(ptr1->next!=nullptr && ptr1!=nullptr){ // 遍历整个链表if(ptr1->next->data==val){ListNode* tmp = ptr1->next;ptr1->next = ptr1->next->next;delete tmp; // 释放掉被删除节点所占用的内存，避免内存泄漏}// 不写 else ，即在这里只写 ptr1=ptr1->next;，程序运行会面临崩溃ptr1=ptr1->next;}

这两种形式的代码有什么区别：

A形式代码中，如果if判断条件不符合，那么程序会执行else分支，即会执行ptr1=ptr1->next;；如果if判断条件符合，那么程序便不会执行else分支，即不会执行ptr1=ptr1->next;。

B形式代码中，无论if判断条件符合或不符合，都会执行 ptr1=ptr1->next; 语句。

这种方法的时间复杂度和空间复杂度如下所示：

让我们分析这段代码的 时间复杂度 和 空间复杂度。

1. 时间复杂度

删除头节点：
  • while (head != nullptr && head->data == val) 这段代码的目标是删除所有满足条件（Node.val == val）的头节点。它会循环遍历链表，直到找到一个不等于 val 的节点或者链表为空。
  • 在最坏的情况下，如果链表中的所有节点的值都等于 val，那么这个 while 循环会遍历整个链表。假设链表有 n 个节点，这个循环的时间复杂度是 O(n)。
删除非头节点：
  • while (ptr1 != nullptr && ptr1->next != nullptr) 这段代码用于遍历链表，删除值为 val 的节点（但不包括头节点）。
  • 在最坏的情况下，这个循环会遍历整个链表一次，假设链表有 n 个节点，所以时间复杂度为 O(n)。
  • 对于每个节点，删除操作本身的时间复杂度是 O(1)（因为只是更新指针并释放内存）。
综合分析：
  • 在最坏的情况下，首先会有一次对整个链表的遍历（删除头节点），然后再进行一次遍历来删除非头节点。因此，整体时间复杂度是 O(n)。

2. 空间复杂度

  • 在代码中，我们只使用了常数空间来存储指针 head、ptr1 和 tmp。这些都是指向链表节点的指针，它们并不随着链表的大小变化而增加。
  • 其他变量（如 val）只是一个简单的整数，也不影响空间复杂度。
  • 我们并没有创建额外的存储结构，如数组、哈希表等来存储节点，因此空间复杂度是 O(1)。

总结：

  • 时间复杂度：O(n)，其中 n 是链表的长度，因为我们需要遍历整个链表两次（一次删除头节点，一次删除非头节点）。
  • 空间复杂度：O(1)，只使用了常数的额外空间来存储指针。

这样，代码的性能较为高效，适用于较长的链表。

3.2 设置虚拟头节点

#include<iostream>
// 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。struct ListNode
{int data; // 定义节点数据域ListNode* next; // 定义节点指针域ListNode(int x) :data(x),next(nullptr){} // 节点的构造函数
};// 设置一个虚拟头结点在进行移除节点操作（不需要单独考虑头节点的删除工作）
ListNode* removeElements_virtualHead(ListNode* head, int val){ListNode* virtualHead = new ListNode(0); // 创建一个虚拟头节点virtualHead->next = head; // 将虚拟头节点指向head// 接下来就是常规的删除非头节点操作ListNode* ptr = virtualHead; // 定义一个遍历指针while(ptr!=nullptr && ptr->next!=nullptr){if(ptr->next->data == val){ListNode* tmp = ptr->next;ptr->next = ptr->next->next;delete tmp;}else{ptr = ptr->next;}}head = virtualHead->next;delete virtualHead;return head;
}int main(){// 定义一个新链表 1--2--6--2ListNode* L_head = new ListNode(1); // 新链表的头节点为L_headL_head->next = new ListNode(2);L_head->next->next = new ListNode(6);L_head->next->next->next = new ListNode(2);int val=2; // 定义要删除的元素ListNode* new_head = removeElements_virtualHead(L_head,val);return 0;
}

分析这段代码的 时间复杂度 和 空间复杂度：

时间复杂度：

  1. 遍历链表：

    • while (ptr != nullptr && ptr->next != nullptr) 循环会遍历整个链表，直到到达链表的最后一个节点（即 ptr->next == nullptr）。所以，这个循环会执行一次链表的遍历。
    • 假设链表的长度是 n，那么该循环最多会执行 n 次。

  2. 删除节点操作：

    • 每次 if 条件满足时，都会删除一个节点。这一操作包括：
      • 查找节点（ptr->next->data == val），这是一个常数时间的操作：O(1)。
      • 将节点从链表中移除（ptr->next = ptr->next->next）也是 O(1)。
      • 删除节点本身（delete tmp）也是 O(1) 操作。
    • 由于每个节点的删除操作都是常数时间的操作，而删除节点的次数最多为 n（即链表中最多有 n 个节点值为 val），所以总的删除操作时间是 O(n)。

  3. 综合分析：

    • 总体来说，代码的时间复杂度是由 遍历链表 和 删除节点操作 两部分组成的。两者都涉及对每个节点的操作，因此时间复杂度是 O(n)。

空间复杂度：

  1. 额外空间：

    • 我们在代码中创建了一个虚拟头节点 virtualHead，这是一个新的节点，所以占用了常数空间：O(1)。
    • 我们还使用了 ptr 和 tmp 两个指针变量，都是常数空间的使用。

  2. 链表本身的空间：

    • 链表的节点是在原地修改的，没有额外创建新的节点，除了虚拟头节点外，其他节点不需要额外的存储空间。

  3. 综合分析：

    • 代码的空间复杂度主要由 virtualHead 和局部指针 ptr、tmp 组成，这些都占用常数空间。
    • 因此，空间复杂度是 O(1)。

结论：

  • 时间复杂度：O(n)，其中 n 是链表的长度。
  • 空间复杂度：O(1)，因为只有常数空间的额外开销。

推荐观看视频：

手把手带你学会操作链表 | LeetCode：203.移除链表元素_哔哩哔哩_bilibili


http://www.ppmy.cn/news/1575535.html

相关文章

常见锁类型介绍

常见锁类型介绍

下面结合代码详细介绍 Mutex、RW Lock、Futex、自旋锁、信号量、条件变量 和 synchronized&#xff0c;并分析它们的适用场景、特点以及为什么这些锁适用于特定场景。我们将从锁的实现机制和性能特点出发&#xff0c;解释其适用性。 1. Mutex&#xff08;互斥锁&#xff09; 代…
阅读更多...
AcWing 蓝桥杯集训·每日一题2025

AcWing 蓝桥杯集训·每日一题2025

题目链接 : 5437. 拐杖糖盛宴 题意: 有m个不同的糖果和n个不同高度的奶龙, 奶龙可以根据自己的身高去吃糖果,糖果垂直于地面,对于一个糖果都需要让每个奶龙尝试能否吃到,如果吃到则减去相应吃到的长度, 奶龙长高吃掉糖果的长度即可,根据长度进行判断, 分类讨论。 解题思路 : …
阅读更多...
英伟达4090显卡ubuntu服务器部署deepseek大模型步骤（vLLM）（未验证）

英伟达4090显卡ubuntu服务器部署deepseek大模型步骤（vLLM）（未验证）

文章目录 一、环境搭建&#xff08;关键步骤&#xff09;二、模型部署&#xff08;推荐vLLM方案&#xff09;1. 启动OpenAI兼容API服务2. 参数说明 三、API调用&#xff08;完全兼容OpenAI协议&#xff09;四、进阶优化建议五、验证流程附&#xff1a;vLLM与原生HuggingFace性能…
阅读更多...
seacmsv9管理员账号+密码注入

seacmsv9管理员账号+密码注入

Seacms v9 SQL 注入漏洞分析与利用 1. 漏洞概述 Seacms&#xff08;海洋 CMS&#xff09;是一款基于 PHP5.X MySQL 架构的视频点播系统&#xff0c;被广泛用于影视站点管理。在 Seacms v9 版本中&#xff0c;./comment/api/index.php 存在 SQL 注入漏洞&#xff0c;漏洞参数…
阅读更多...
本地部署DeepSeek全攻略：Ollama+Chatbox保姆级教程

本地部署DeepSeek全攻略：Ollama+Chatbox保姆级教程

目录 缘起 为什么需要本地部署&#xff1f; 硬件要求建议&#xff1a; 下载Ollama 安装准备 选择对应的平台下载 下载完成点击安装 install 安装完成后验证 win r打开运行窗口 输入cmd打开命令行窗口 输入ollama&#xff0c;看到有这些输出就代表安装ollama成功啦 …
阅读更多...
ubuntu下r8125网卡重启丢失修复案例一则

ubuntu下r8125网卡重启丢失修复案例一则

刚装的一台服务器&#xff0c;ubuntu24.04&#xff0c;主板网卡是r8125&#xff0c;安装服务后会莫名其妙丢失驱动 按照官网的方法下载最新8125驱动包&#xff1a; Realtek 然后卸载驱动 rmmod r8125 然后在驱动包里安装&#xff08;幸好我之前装了build-essential&#x…
阅读更多...
eclasticsearch文档搜索

eclasticsearch文档搜索

版本选择&#xff0c;参考&#xff1a;https://blog.csdn.net/2301_79098963/article/details/138275506 下载elasticsearch-7-10-0&#xff0c;选择windows版本&#xff0c;zip包解压到指定目录即可 https://www.elastic.co/downloads/past-releases/elasticsearch-7-10-0 对…
阅读更多...
Linux-IPC-共享内存

Linux-IPC-共享内存

Linux IPC 之 共享内存&#xff08;Shared Memory&#xff09; 共享内存&#xff08;Shared Memory&#xff09;是Linux 进程间通信&#xff08;IPC&#xff09;的一种方式&#xff0c;它允许多个进程访问同一块内存区域&#xff0c;从而避免频繁的数据复制&#xff0c;提高效…
阅读更多...
最新文章

Copyright @ 2022~2023