合并零之间的节点

难度: Medium

给你一个链表的头节点 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 * 10⁵] 内
0 <= Node.val <= 1000
不存在连续两个 Node.val == 0 的节点
链表的开端和末尾节点都满足 Node.val == 0

Submission

运行时间: 2428 ms

内存: 183.1 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = head
        cur = pre.next
        if cur is None:
            return
        s = 0
        while cur.val != 0:
            s += cur.val
            cur = cur.next
        n = ListNode(s)
        pre.next.val = s
        pre.next.next = self.mergeNodes(cur)
        return head.next

Explain

该题解使用递归方法来合并链表中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)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = head  # 初始的前置节点
        cur = pre.next  # 当前正在处理的节点
        if cur is None:  # 如果当前节点为None，直接返回
            return
        s = 0  # 用于累加当前段的节点值
        while cur.val != 0:  # 当当前节点值不为0时，继续累加
            s += cur.val
            cur = cur.next
        n = ListNode(s)  # 创建新节点，值为累加和
        pre.next.val = s  # 更新pre的next节点的值为s
        pre.next.next = self.mergeNodes(cur)  # 递归处理cur之后的链表，并链接
        return head.next  # 返回处理后的链表头，即去掉了最初的0节点

Explore

在题解中的逻辑中，遇到连续的0节点时，会创建一个值为0的新节点。从技术角度看，当cur遍历到第一个0后，s被设置为0（累加和初始化），然后遇到下一个0时，因为没有遇到非0值节点，s仍然为0。因此，这段代码会创建一个值为0的节点，然后继续递归处理后续链表。这确保了连续的0节点被正确处理，每两个连续的0之间会插入一个值为0的新节点。

是的，原始的头节点head在递归过程中未被修改。这是因为原始的head节点作为函数的一个静态起点，始终指向链表的最初位置。在合并过程中，我们不需要改变head节点本身，而是修改head.next来指向合并后的新链表。返回head.next是为了去除链表起始的0节点，这样，返回的链表直接从合并后的第一个有效节点开始，使得结果链表更符合题目要求。

是的，递归方法依赖于调用栈来保存函数调用的状态，每进行一次递归调用，就会消耗一定的栈空间。如果链表非常长，尤其是包含很多个0节点时，递归调用的深度可能会非常深，从而有可能导致栈溢出错误。在实际应用中，如果链表长度极大，可能需要考虑使用迭代方法来替代递归，以避免栈溢出的风险。

在题解的逻辑中，如果链表仅包含一个0节点，cur初始化为head.next，此时head.next是None。由于cur是None，函数会直接返回None。这意味着函数返回的结果也是None，而不包含任何节点。这是符合题目要求的，因为输入链表仅包含一个0节点时，合并后应没有任何内容，即返回一个空链表。