当前位置: 首页 > news >正文

2181、合并零之间的节点

2181、[中等] 合并零之间的节点

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.mrgr.cn/news/62602.html

相关文章:

  • 《神经网络助力战场车辆及部件损毁识别与评估》
  • Android 获取OAID
  • 【Stable Diffusion】
  • QT 周期性的杀死一个进程(软件),一分钟后自动退出
  • git回滚间隔的提交
  • k8s环境下rabbitmq安装社区插件:rabbitmq_delayed_message_exchange
  • YOLOv4和Darknet实现坑洼检测
  • 如何成为一名优秀的程序员,进来看看
  • 网络安全不知道怎么学,看完这篇,中学生都能学会
  • iOS 再谈KVC、 KVO
  • 阿里CDN框架
  • 前端实现echarts折线图堆叠(多条折线)
  • Jupyter notebook 添加目录插件
  • 一致校验矩阵计算
  • kdd比赛方案
  • 基于Python的PostgreSQL数据库操作示例(三)
  • 笔记本双系统win10+Ubuntu 20.04 无法调节亮度亲测解决
  • Istio_04_Istio可观测性
  • 一:Linux学习笔记(第一阶段)-- 安装软件 vmware workstation 虚拟机软件 centos系统
  • vue3使用vite设置 @ 路径别名指向src 目录
  • mac-ubuntu虚拟机(扩容-共享-vmtools)
  • 如何预防Kubernetes安全漏洞
  • 如何创建一个网站?
  • 【hacker送书第14期】AI训练师算法与模型训练从入门到精通
  • 9、node.js和Lowdb
  • 知网中的复合影响因子和综合影响因子解析