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; // 移动到下一个节点}// 确保新链表的末尾指向 nullptrnewcur->next = nullptr;// 返回合并后链表的头节点，跳过哨兵节点return newhead.next;}
};

4、时间复杂度：

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