本文主要是介绍【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)
题目描述
给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。
思路分析
-
初始化:创建一个虚拟头节点
dummy
,用于构建新的链表。同时,定义一个变量sum
用于累加两个 0 之间的节点值。 -
遍历链表:从头节点的下一个节点开始遍历链表,因为头节点的值总是 0。
-
处理非零节点:当遇到非零节点时,将其值累加到
sum
中。 -
处理零节点:当遇到零节点时,表示一个区间的结束。如果
sum
大于 0,则创建一个新的节点,其值为sum
,并将这个新节点添加到新链表中。然后重置sum
为 0,以便于累加下一个区间的值。 -
跳过连续的零:题目保证不会出现连续两个非零节点之间的零节点,因此不需要额外处理。
-
返回结果:遍历完成后,返回
dummy.next
作为新链表的头节点。
输入示例
-
输入:head = [0,3,1,0,4,5,2,0]
-
输出:[4,11]
-
解释:
上图表示输入的链表。修改后的链表包含: -
标记为绿色的节点之和:3 + 1 = 4
-
标记为红色的节点之和:4 + 5 + 2 = 11
-
输入:head = [0,1,0,3,0,2,2,0]
-
输出:[1,3,4]
-
解释:
上图表示输入的链表。修改后的链表包含: -
标记为绿色的节点之和:1 = 1
-
标记为红色的节点之和:3 = 3
-
标记为黄色的节点之和:2 + 2 = 4
代码实现
/*** 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 current = dummy; // current 指向新链表的当前节点int sum = 0; // 用于累加区间节点的值// 跳过开头的 0,开始遍历head = head.next;while (head != null) {if (head.val == 0) { // 遇到 0,表示一个区间的结束if (sum > 0) { // 如果 sum 大于 0,则创建新节点并添加到新链表中current.next = new ListNode(sum);current = current.next; // 移动 current 到新节点sum = 0; // 重置 sum 为 0,准备下一个区间}} else {// 累加非零节点的值sum += head.val;}head = head.next; // 移动到下一个节点}return dummy.next; // 返回新链表的头节点}
}
这篇关于【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!