Easy Intuitive 2 Solutions || With and Without using extra space ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to merge nodes between consecutive zeros into a single node whose value is 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to merge nodes between consecutive zeros into a single node whose value is the sum of all the nodes between these zeros. The linked list should not contain any zeros after this merging process.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n##### 1. Dummy Node:\n\n- Use a `dummy` node to simplify the creation of the new linked list. The dummy node acts as a placeholder to easily return the head of the new list. \n##### 2. Traverse the List:\n\n- Use a pointer temp to traverse the input list starting from the first node after the initial zero.\n- Maintain a pointer current to construct the new list.\n##### 3. Sum Calculation:\n\n- Initialize a `sum` variable to accumulate values between zeros.\n- Traverse through the list, adding node values to the sum until a zero is encountered.\n\n##### 4. Update New List:\n\n- When a zero is encountered, create a new node with the sum value and add it to the new list.\n- Reset the sum to zero and continue to the next segment.\n\n##### 5. Return Result:\n\n- The head of the new list is `dummy->next`, as the dummy node is a placeholder.\n\n# Complexity\n- Time complexity: $O(n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:  $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        ListNode* dummy = new ListNode(0);  // Dummy node to start the new list\n        ListNode* current = dummy;          // Pointer to the current node in the new list\n        \n        ListNode* temp = head->next;  // Start from the first node after the initial zero\n        int sum = 0;\n\n        while (temp != nullptr) {\n            if (temp->val == 0) {\n                // When a zero is encountered, add a new node with the sum to the new list\n                current->next = new ListNode(sum);\n                current = current->next;\n                sum = 0;  // Reset sum for the next segment\n            } else {\n                // Add the value to the sum\n                sum += temp->val;\n            }\n            temp = temp->next;\n        }\n        \n        return dummy->next;  // Return the next of dummy node, as dummy is a placeholder\n    }\n};\n\n```\n---\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires merging nodes between consecutive zeros into a single node containing the sum of those nodes. This needs to be done in place, modifying the original linked list without creating a new one. The key is to traverse the list, calculate sums for segments between zeros, and update the list nodes accordingly.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n##### 1. Initialization:\n\n- Start traversing from the first node after the initial zero.\n- Use two pointers: current to traverse the list and result to build the new list in place.\n##### 2. Traversal and Sum Calculation:\n\n- Traverse the list using the current pointer.\n- For each segment of nodes between two zeros, sum the values of the nodes.\n##### 3. Update List:\n\n- Store the calculated sum in the node pointed to by the result pointer.\n- Move the result pointer to the next node in the list only if there are more nodes to process.\n##### 4. Remove Trailing Zeros:\n\n- After processing all nodes, set the next pointer of the last valid node to nullptr to remove any trailing zeros.\n\n# Complexity\n- Time complexity: $O(n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:  $O(1)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        ListNode* current = head->next;  // Skip the initial zero\n        ListNode* result = head;         // Pointer to construct the new list in place\n        \n        while (current != nullptr) {\n            int sum = 0;\n\n            // Sum nodes until the next zero\n            while (current != nullptr && current->val != 0) {\n                sum += current->val;\n                current = current->next;\n            }\n            \n            // Store the sum in the result node\n            result->val = sum;\n            \n            // Move result pointer if not at the end\n            if (current != nullptr) {\n                current = current->next;  // Skip the zero\n                if (current != nullptr) {\n                    result = result->next;\n                }\n            }\n        }\n        \n        // Remove the trailing zeros by setting the next pointer of the last node to nullptr\n        result->next = nullptr;\n\n        return head;\n    }\n};\n\n```\n\n> ### Upvote, if you are still reading! \u2B06\uFE0F
['Linked List', 'C++']