LeetCode:2181. 合并零之间的节点 遍历链表

2181. 合并零之间的节点

today 2181. 合并零之间的节点

题目描述

给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的开端和末尾的节点都满足Node.val == 0 。

对于每两个相邻的0，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。

返回修改后链表的头节点 head 。

示例1：

 输入：head = [0,3,1,0,4,5,2,0]
 输出：[4,11]
 解释：	
 修改后的链表包含：
 - 合并 [3,1,4,5] 得到 4 。
 - 合并 [1,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 * 105] 内
• 0 <= Node.val <= 1000
• 不 存在连续两个Node.val == 0的节点
• 链表开端和末尾的节点都满足 Node.val == 0

题目解析

为了解决这个问题，我们可以使用双指针遍历链表，同时用一个辅助链表来构建新的链表。思路大致如下：

1. 遍历原链表，遇到的节点值不为0时，将节点值增加到cur_val中。遇到0时，创建新的节点，节点值为cur_val，并将cur_val置为0。
2. 将新创建的节点添加到辅助链表中。
3. 重复步骤1和步骤2，直到遍历完原链表。
4. 最后，返回新的链表的头节点。

复杂度分析：

• 时间复杂度：$O(n)$，遍历原链表一次，合并节点一次，所以时间复杂度为 $O(n)$
• 空间复杂度：$O(n)$，创建新的链表，所以空间复杂度为 $O(n)$

代码实现

Python版本：

class Solution(object):
    def mergeNodes(self, head):
        dummpy = ListNode(0)
        cur = dummpy
        cur_val = 0
        while head:
            if head.val==0 and cur_val!=0:
                new_node= ListNode(cur_val)
                cur.next=new_node
                cur=new_node
                cur_val=0
            else:
                cur_val+=head.val
            head=head.next
        return dummpy.next

C++版本：

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        ListNode* res=new ListNode(0);
        int curVal=0;
        ListNode* curNode=res;
        while(head->next!=nullptr){
            head=head->next;
            if(head->val==0){
                ListNode* newNode=new ListNode(curVal);
                curNode->next=newNode;
                curNode=newNode;
                curVal=0;
            }else{
                curVal+=head->val;
            }
        }
        return res->next;
    }
};

Go版本：

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        ListNode* res=new ListNode(0);
        int curVal=0;
        ListNode* curNode=res;
        while(head->next!=nullptr){
            head=head->next;
            if(head->val==0){
                ListNode* newNode=new ListNode(curVal);
                curNode->next=newNode;
                curNode=newNode;
                curVal=0;
            }else{
                curVal+=head->val;
            }
        }
        return res->next;
    }
};