# LeetCode 2181. Merge Nodes in Between Zeros
[LeetCode 2181. Merge Nodes in Between Zeros](https://leetcode.com/problems/merge-nodes-in-between-zeros) (<font color=#FFB800>Medium</font> 89.9%)
<!--
(<font color=#00AF9B>Easy</font> 53.8%)
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
-->

- 限制 :

<ul>
<li><code>The number of nodes in the list is in the range [3, 2 * 105].</code></li>
<li><code>0 <= Node.val <= 1000</code></li>
<li><code>There are no two consecutive nodes with Node.val == 0.</code></li>
<li><code>The beginning and end of the linked list have Node.val == 0.</code></li>
</ul>

- Solution 1
其實就是從頭到尾跑一次，然後把0 和 0中間的值加起來，就是答案。
- 時間複雜度: $O(n)$
- 空間複雜度: $O(1)$

- 程式碼

    class Solution {
    public:
        ListNode* mergeNodes(ListNode* head) {
            ListNode* result = new ListNode();
            ListNode* now = result;
            ListNode* index = head;
            while (index->next != nullptr) {
                if (index->val == 0) {
                    ListNode* temp = new ListNode();
                    now->next = temp;
                    now = now->next;
                } else {
                    now->val += index->val;
                }
                index = index->next;
            }
            return result->next;
        }
    };

- Solution 2
同樣手法，只是為稍微減少記憶體，所以使用原有的 Linked list 作為存放答案的地方；並且在歷遍的地方也稍微修改來加快一點速度。
- 時間複雜度: $O(n)$
- 空間複雜度: $O(1)$

- 程式碼

    class Solution {
    public:
        ListNode* mergeNodes(ListNode* head) {
            ios_base::sync_with_stdio(false);
            cin.tie(NULL);
            cout.tie(NULL);

            ListNode* sumNode = head;
            ListNode* indexNode = head->next;
            int sum = 0;
            while (indexNode != nullptr) {
                if (indexNode->val == 0) {
                    sumNode->val = sum;
                    if (indexNode->next == nullptr)
                        break;
                    sumNode = sumNode->next;
                    sum = 0;
                } else {
                    sum += indexNode->val;
                }
                indexNode = indexNode->next;
            }
            sumNode->next = nullptr;
            return head;
        }
    };