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; // 移动到下一个节点
        }

        // 确保新链表的末尾指向 nullptr
        newcur->next = nullptr;

        // 返回合并后链表的头节点，跳过哨兵节点
        return newhead.next;
    }
};

4、时间复杂度：

• 时间复杂度：O(n)，其中 n 是链表中节点的数量。我们只需要遍历链表一次。
• 空间复杂度：O(1)，只用了常数空间来存储累加值和指针。