合并零之间的节点
难度:
标签:
题目描述
给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。
返回修改后链表的头节点 head 。
示例 1：
输入：head = [0,3,1,0,4,5,2,0] 输出：[4,11] 解释： 上图表示输入的链表。修改后的链表包含： - 标记为绿色的节点之和：3 + 1 = 4 - 标记为红色的节点之和：4 + 5 + 2 = 11
示例 2：
输入：head = [0,1,0,3,0,2,2,0] 输出：[1,3,4] 解释： 上图表示输入的链表。修改后的链表包含： - 标记为绿色的节点之和：1 = 1 - 标记为红色的节点之和：3 = 3 - 标记为黄色的节点之和：2 + 2 = 4
提示：
- 列表中的节点数目在范围
[3, 2 * 105]内 0 <= Node.val <= 1000- 不 存在连续两个
Node.val == 0的节点 - 链表的 开端 和 末尾 节点都满足
Node.val == 0
代码结果
运行时间: 2428 ms, 内存: 183.1 MB
/*
思路：
1. 使用Stream流来简化遍历过程。
2. 创建一个新的节点保存每个部分的和。
*/
import java.util.stream.Stream;
public class Solution {
public ListNode mergeNodes(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
Stream.iterate(head.next, node -> node != null, node -> node.next)
.map(node -> node.val)
.filter(val -> val != 0)
.reduce((acc, val) -> acc + val)
.ifPresent(sum -> tail.next = new ListNode(sum));
return dummy.next;
}
}解释
方法:
该题解使用递归方法来合并链表中0之间的节点。首先，它初始化两个指针，pre和cur，其中pre指向头节点head，cur指向head的下一个节点。它检查cur是否为None，如果是，则直接返回，这是基本的边界条件。在一个循环中，当cur指向的节点值不为0时，累加这些节点的值到变量s中，并将cur向前移动。当遇到值为0的节点时，结束当前区间的合并，创建一个新的节点n，其值为s，然后递归地对cur后面的链表进行相同的操作，将结果链接到当前创建的节点n后。递归结束后，返回head.next，即去掉了最初的0节点的新链表。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在递归调用中，如何处理如果链表中有连续的0节点的情况？例如输入链表为[0,0,1,2,0]，该如何确保正确合并节点？
▷🦆
题解中提到递归结束后返回head.next，这是否意味着原始的头节点head在递归过程中始终未被修改？如果是这样，为什么选择保留原始头节点？
▷🦆
题解中的递归逻辑是基于每次遇到0时创建新节点并递归处理后续链表，这种方法在处理非常长的链表时是否有栈溢出的风险？
▷🦆
题解中提到，当cur是None时直接返回，这种处理方式是否能正确处理输入链表仅包含一个0节点的情况？
▷