博罗网站制作公司项目建设网站大全
2181、[中等] 合并零之间的节点
1、问题描述：
给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。
返回修改后链表的头节点 head 。
2、代码思路：
- 跳过第一个节点：链表的开头和结尾都包含值为
0的节点，我们从第二个节点开始处理（即head->next）。 - 累加节点值：对于每两个
0之间的节点，累加它们的值。 - 遇到
0时创建新节点：当遇到0时，将前面累加的值创建一个新的节点，插入到新链表中。 - 继续遍历：继续遍历链表，重复上述步骤，直到遍历完整个链表。返回合并后的新链表，忽略初始的哨兵节点。
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)，只用了常数空间来存储累加值和指针。