2181、合并零之间的节点

embedded/2025/2/3 18:46:14/

2181、leetcode.cn/problems/merge-nodes-in-between-zeros/description/" rel="nofollow">[中等] 合并零之间的节点

1、问题描述:

给你一个链表的头节点 head ,该链表包含由 0 分隔开的一连串整数。链表开端末尾 的节点都满足 Node.val == 0

对于每两个相邻的 0 ,请你将它们之间的所有节点合并成一个节点,其值是所有已合并节点的值之和。然后将所有 0 移除,修改后的链表不应该含有任何 0

返回修改后链表的头节点 head

2、代码思路:

  1. 跳过第一个节点链表的开头和结尾都包含值为 0 的节点,我们从第二个节点开始处理(即 head->next)。
  2. 累加节点值:对于每两个 0 之间的节点,累加它们的值。
  3. 遇到 0 时创建新节点:当遇到 0 时,将前面累加的值创建一个新的节点,插入到新链表中。
  4. 继续遍历:继续遍历链表,重复上述步骤,直到遍历完整个链表。返回合并后的新链表,忽略初始的哨兵节点。

3、代码实现与详细注释

class Solution {
public:ListNode* mergeNodes(ListNode* head) {// 创建一个新的链表头,用来存储合并后的结果链表ListNode newhead; // 一个新链表的头节点(哨兵节点)ListNode *newcur = &newhead; // 用于遍历新链表的指针,初始化指向哨兵节点ListNode *cur = head->next;  // 当前链表从 head->next 开始,因为 head 是 0,忽略它int sum = 0; // 用于累加两个 0 之间的节点的值// 遍历原始链表,直到结束while (cur) {// 遇到值为 0 的节点时,说明需要合并并创建新节点if (cur->val == 0) {// 创建新节点,节点值为前面累加的 sum 值ListNode* newnode = new ListNode(sum);sum = 0; // 重置 sum,准备下一组合并newcur->next = newnode; // 将新节点链接到结果链表newcur = newcur->next;  // 移动指针到新节点,准备接受下一个合并节点} else {// 如果不是 0,则累加当前节点的值sum += cur->val;}cur = cur->next; // 移动到下一个节点}// 确保新链表的末尾指向 nullptrnewcur->next = nullptr;// 返回合并后链表的头节点,跳过哨兵节点return newhead.next;}
};

4、时间复杂度:

  • 时间复杂度:O(n),其中 n链表中节点的数量。我们只需要遍历链表一次。
  • 空间复杂度:O(1),只用了常数空间来存储累加值和指针。

http://www.ppmy.cn/embedded/159242.html

相关文章

minimind - 从零开始训练小型语言模型

大语言模型(LLM)领域,如 GPT、LLaMA、GLM 等,虽然它们效果惊艳, 但动辄10 Bilion庞大的模型参数个人设备显存远不够训练,甚至推理困难。 几乎所有人都不会只满足于用Lora等方案fine-tuing大模型学会一些新的…

【开源免费】基于SpringBoot+Vue.JS体育馆管理系统(JAVA毕业设计)

本文项目编号 T 165 ,文末自助获取源码 \color{red}{T165,文末自助获取源码} T165,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…

LeetCode435周赛T2贪心

题目描述 给你一个由字符 N、S、E 和 W 组成的字符串 s,其中 s[i] 表示在无限网格中的移动操作: N:向北移动 1 个单位。S:向南移动 1 个单位。E:向东移动 1 个单位。W:向西移动 1 个单位。 初始时&#…

ubuntu 下使用deepseek

安装Ollama sudo snap install ollama 执行 ollama run deepseek-coder 然后进行等待。。。

【apt源】RK3588 平台ubuntu20.04更换apt源

RK3588芯片使用的是aarch64架构,因此在Ubuntu 20.04上更换apt源时需要使用针对aarch64架构的源地址。以下是针对RK3588芯片在Ubuntu 20.04上更换apt源到清华源的正确步骤: 步骤一:打开终端 在Ubuntu 20.04中,按下Ctrl Alt T打…

Python学习之旅:进阶阶段(五)数据结构-双端队列(collections.deque)

在 Python 的进阶学习过程中,数据结构的掌握至关重要。今天要介绍的双端队列(deque,即 double-ended queue),是一种非常实用的数据结构,Python 的collections模块中的deque类为我们提供了强大的双端队列操作功能。接下来,就一起深入了解双端队列吧。 一、什么是双端队列…

解决国内服务器 npm install 卡住的问题

在使用国内云服务器时,经常会遇到 npm install 命令执行卡住的情况。本文将分享一个典型案例以及常见的解决方案。 问题描述 在执行以下命令时: mkdir test-npm cd test-npm npm init -y npm install lodash --verbose安装过程会卡在这个状态&#xf…

【B站保姆级视频教程:Jetson配置YOLOv11环境(六)PyTorchTorchvision安装】

Jetson配置YOLOv11环境(6)PyTorch&Torchvision安装 文章目录 1. 安装PyTorch1.1安装依赖项1.2 下载torch wheel 安装包1.3 安装 2. 安装torchvisiion2.1 安装依赖2.2 编译安装torchvision2.2.1 Torchvisiion版本选择2.2.2 下载torchvisiion到Downloa…