​LeetCode解法汇总1171. 从链表中删去总和值为零的连续节点

news/2024/10/9 11:49:33/

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。

删除完毕后,请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)

示例 1:

输入:head = [1,2,-3,3,1]
输出:[3,1]
提示:答案 [1,2,1] 也是正确的。

示例 2:

输入:head = [1,2,3,-3,4]
输出:[1,2,4]

示例 3:

输入:head = [1,2,3,-3,-2]
输出:[1]

提示:

  • 给你的链表中可能有 1 到 1000 个节点。
  • 对于链表中的每个节点,节点的值:-1000 <= node.val <= 1000.

解题思路:

* 解题思路:

* 构建前缀和,相同前缀和的位置,其连续累加值必定为0,相同前缀和之间的节点都是可以被删掉的。

* 另外,如果有多个前缀和都相同的节点,我们只需要取第一个和最后一个即可。

* 所以构建一个map,key为前缀和,value则为对应的节点。

* 首先遍历第一遍,找到最后一个前缀和的节点加入到map中。

* 然后第二遍循环,找到等于当前前缀和值的节点,这时候是一定存在的,是不过有可能是当前的节点。

* 如果是当前节点的话,使用node->next = seen[prefix]->next;也满足要求。

代码:

class Solution1171
{
public:ListNode *removeZeroSumSublists(ListNode *head){ListNode *newHead = new ListNode(0);newHead->next = head;int prefix = 0;map<int, ListNode *> seen;for (ListNode *node = newHead; node; node = node->next){prefix += node->val;seen[prefix] = node;}prefix = 0;for (ListNode *node = newHead; node; node = node->next){prefix += node->val;node->next = seen[prefix]->next;}return newHead->next;}
};


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

相关文章

电脑重装系统后需要更新哪些驱动

在电脑重装系统后&#xff0c;由于系统的重置&#xff0c;您需要重新安装和更新一些关键的驱动程序&#xff0c;以确保硬件设备正常工作和性能最佳化。以下是在电脑重装系统后需要更新的一些常见驱动程序。 工具/原料&#xff1a; 系统版本&#xff1a;win10系统 品牌型号&…

iOS App 上架流程图文教学

在上架App 之前必须先准备好开发者帐号&#xff0c;但申请开发者帐号因法兰克早在之前已经申请好了&#xff0c;故就跳过此步骤&#xff0c;直接从产生凭证到上传App开始讲起。首先&#xff0c;要将自己辛苦写好的App 送审的话&#xff0c;则要依序做完下列几件事情即可。 在开…

云计算——云计算与虚拟化的关系

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​ 目录 前言 一.虚拟化 1.什么是虚拟化 2.虚拟化技术作用 二.云计算与虚拟化的关系 三.虚…

PHP设计模式21-工厂模式的讲解及应用

文章目录 前言基础知识简单工厂模式工厂方法模式抽象工厂模式 详解工厂模式普通的实现更加优雅的实现 总结 前言 本文已收录于PHP全栈系列专栏&#xff1a;PHP快速入门与实战 学会好设计模式&#xff0c;能够对我们的技术水平得到非常大的提升。同时也会让我们的代码写的非常…

虚拟机全屏太小,如何放大

干货&#xff01;&#xff01;&#xff01; 点击虚拟机右上角的电源图表、&#xff0c;找到螺丝刀扳手图标、搜索Display更改分辨率、确认更改问题解决&#xff01;&#xff01;&#xff01;

有效减小虚拟机占的内存

我这个电脑内存少&#xff0c;D盘才350g,结果kali占了300g,主要的原因还是我的快照拍了比较多&#xff0c;平常拍快照可以避免我们操作失误导致系统崩溃&#xff0c;就算崩溃了还可以还原&#xff0c;这样确实挺好&#xff0c;但快照很占内存&#xff0c;如果是分散的快照还行&…

玩游戏计算机虚拟内存怎么设置,玩游戏时提示虚拟内存太小怎么办

小编这里要跟大家分享的是关于玩游戏时提示虚拟内存太小的解决方法&#xff0c;游戏是如今很多人在业余时间用来消遣和放松的方式&#xff0c;电脑运行顺畅是玩游戏必备的条件之一&#xff0c;否则就会很扫兴&#xff0c;但是一些用户反映&#xff0c;好不容易想要玩一把游戏的…

服务器虚拟内存最佳设置范围,虚拟内存有什么用?虚拟内存设置多少合适?

在硬盘上划分一块区域用于保存内存中暂时不用的数据&#xff0c;这块区域称为虚拟内存。相对于硬盘空间来说&#xff0c;内存容量往往小得多&#xff0c;尤其是2005 年以前(128MB、256MB)&#xff0c;现在内存容量增加不少&#xff0c;最小的都有4GB&#xff0c;大的有64GB、12…