2181. 合并零之间的节点（24.9.9）

题目

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

解题思路

见代码

代码

非原地+末尾特殊处理

设一个值sum专门用于统计两个0之间的数之和，然后再赋值给 head所对应的位置(即答案所对应的位置)，最后一个0 需要特殊处理，因为其再统计到最后一个0 时就检测到其下一个位置就要离开链表，无法进行赋值操作了，将其赋值给 head的对应的位置，并将其下一个位置赋值为NULL。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeNodes(ListNode* head) {auto tail=head;int sum=0;for(auto i=head->next;i->next;i=i->next){sum+=i->val;//cout<<sum<<endl;if(i->val==0){tail->val=sum;tail=tail->next;sum=0;}}tail->val=sum;tail->next=NULL;return head;}
};

原地

再原地进行操作，再 head最终答案位置直接加上两个0之间的数之和(注：此处位置的值首先要重新赋值为0，因为可能其本身的值不为0)，最后并将其下一个位置赋值为NULL。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeNodes(ListNode* head) {auto tail=head;for(auto i=head->next;i->next;i=i->next){tail->val+=i->val;if(i->val==0){tail=tail->next;tail->val=0;}}tail->next=NULL;return head;}
};

补充

在使用完将其余的释放（在原地算法中进行修改）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeNodes(ListNode* head) {auto tail=head;for(auto i=head->next;i->next;i=i->next){tail->val+=i->val;if(i->val==0){tail=tail->next;tail->val=0;}}auto toDelete = tail->next;tail->next=NULL;while (toDelete) {auto nextToDelete = toDelete->next;delete(toDelete);toDelete = nextToDelete;}return head;}
};