首页 > 编程语言 >[LeetCode] 2181. Merge Nodes in Between Zeros

[LeetCode] 2181. Merge Nodes in Between Zeros

时间:2024-09-09 10:37:51浏览次数:11  
标签:ListNode cur val sum list next Merge 2181 Zeros

You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list will have Node.val == 0.

For every two consecutive 0's, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0's.

Return the head of the modified linked list.

Example 1:
Example 1
Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation:
The above figure represents the given linked list. The modified list contains

  • The sum of the nodes marked in green: 3 + 1 = 4.
  • The sum of the nodes marked in red: 4 + 5 + 2 = 11.

Example 2:
Example 2
Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation:
The above figure represents the given linked list. The modified list contains

  • The sum of the nodes marked in green: 1 = 1.
  • The sum of the nodes marked in red: 3 = 3.
  • The sum of the nodes marked in yellow: 2 + 2 = 4.

Constraints:
The number of nodes in the list is in the range [3, 2 * 105].
0 <= Node.val <= 1000
There are no two consecutive nodes with Node.val == 0.
The beginning and end of the linked list have Node.val == 0.

合并零之间的节点。

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

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

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

思路

这是链表类的简单题,请直接参考代码注释。

复杂度

时间O(n)
空间O(1)

代码

Java实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeNodes(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        ListNode cur = head;
        int sum = 0;
        while (cur != null) {
			// 遇到0就开始计算0之间的node的和
            if (cur.val == 0) {
                sum = 0;
                cur = cur.next;
                while (cur != null && cur.val != 0) {
                    sum += cur.val;
                    cur = cur.next;
                }
				// 遇到下一个0或者list结尾就把之前计算的和放到新的node中
                if (sum != 0) {
                    p.next = new ListNode(sum);
                    p = p.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

标签:ListNode,cur,val,sum,list,next,Merge,2181,Zeros
From: https://www.cnblogs.com/cnoodle/p/18404076

相关文章

  • C# split big file into small files as, and merge the small files into big one
    namespaceConsoleApp59{internalclassProgram{staticstringpath=System.IO.Path.GetDirectoryName(System.Reflection.Assembly.GetExecutingAssembly().Location);staticvoidMain(string[]args){stringfilePa......
  • IDEA中使用git合并分支的过程报错:cant checkout because of unmerged files
    使用idea的git插件控制代码分支合并时,由于操作不当,报错了,控制台报错如下:cantcheckoutbecauseofunmergedfiles,youhavetoresolveallmergeconflictsbeforecheckout.仔细回想报错的起因,经过大概是这样的:首先,远程仓库里面的代码版本是很老了,而本地的代码版......
  • 【原创软件】第10期:PDFCrossMergeV1.0-实现两个PDF交叉合并,适用于PDF扫描件合并,单文件
    解决问题:扫描件合并,由于大部分扫描件是正面一个pdf,反面一个pdf,尤其是正面顺序,反面逆序的pdf,需要交叉合并,也就是说适合单面扫描文件合并。即解决【正面顺序,反面逆序】文件A,扫描文件页码顺序:1、3、5、7、9。文件B,扫描文件页码顺序:10、8、6、4、2。这种合并问题。合并结果是1、2、3......
  • PDF 文件处理PDF合并和拆分工具PDF Merge PDF Splitter for Mac
    “PDFMergePDFSplitterforMac”是一款专门为Mac用户打造的出色PDF文件处理工具。它集合并与拆分PDF文件的核心功能于一体,能极大地方便用户对PDF文档的管理。      软件下载地址在合并功能上,它能迅速将多个PDF文件整合成一个,无论是工作报告、学习资......
  • clickhouse_mergeTree
    MergeTree类型Clickhouse中最强大的表引擎当属MergeTree(合并树)引擎及该系列(*MergeTree)中的其他引擎。MergeTree系列的引擎被设计用于插入极大量的数据到一张表当中。数据可以以数据片段的形式一个接着一个的快速写入,数据片段在后台按照一定的规则进行合并。相比在插入时不......
  • 排序算法 归并排序 MergeSort -- C语言实现
    归并排序归并排序(Mergesort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个非常典型的应用。作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第2种方法);自下......
  • leetcode 2181.合并零之间的结点
    1.题目要求:/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*mergeNodes(structListNode*head){structListNode*cur=head;intcount=0;//1.遍历结......
  • leetcode 2181.合并零之间的结点
    1.题目要求:/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*mergeNodes(structListNode*head){structListNode*cur=head;intcount=0;//1.遍历结......
  • 1003 Emergency
    Asanemergencyrescueteamleaderofacity,youaregivenaspecialmapofyourcountry.Themapshowsseveralscatteredcitiesconnectedbysomeroads.Amountofrescueteamsineachcityandthelengthofeachroadbetweenanypairofcitiesaremarke......
  • CF1499E Chaotic Merge
    对于\(l_1=1,r_1=1\)的情况,设\(f_{i,j,0/1,S}\)表示\(\texttt{x}\)串考虑了前\(i\)个位置,\(\texttt{y}\)串考虑了前\(j\)个位置,且最后一个位置选了\(\texttt{x}\)串还是\(\texttt{y}\)串,选的串的集合为\(S\)的方案数。转移显然。答案为\(\sum_{i=1}^n\sum_{j=1......