💯✅🔥Detailed Easy Java ,Python3 ,C++ Solution|| 4 ms ||≧◠‿◠≦✌
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this approach is to use the first node between two zeros as a mark
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind this approach is to use the first node between two zeros as a marker to store the sum of all the nodes between them. By recursively calling the mergeNodes function on the remaining part of the list, we can calculate the sum of all the nodes between the next two zeros and assign it to the corresponding marker node.\n\n---\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach is to traverse the linked list and calculate the sum of all the nodes between two consecutive zeros. The sum is then assigned to the first node between the two zeros, and the process is repeated recursively until the end of the list is reached.\n\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# Step by Step Explanation\nSure! Let\'s go through the step-by-step explanation of merging the nodes in the list [0, 3, 1, 0, 4, 5, 2, 0] using the `mergeNodes` function.\n\n1. Initial state:\n   ```\n   0 -> 3 -> 1 -> 0 -> 4 -> 5 -> 2 -> 0\n   ```\n\n2. Recursive call: `mergeNodes(head)`\n   - Base case: `head.next` is not null, so we proceed to the next step.\n\n3. Fetch sum from current 0 to next 0:\n   - `ptr` is initialized to `head.next`, pointing to the first node after the first zero.\n   - `sum` is initialized to 0.\n   - We traverse the list using `ptr` until we reach the next zero.\n     - `ptr` points to 3, `sum` is updated to 3.\n     - `ptr` points to 1, `sum` is updated to 4.\n     - `ptr` points to 0, we stop the loop since we found the next zero.\n\n4. Assign sum on the first node between nodes having value 0:\n   - We assign the value of `sum` (4) to the first node between the two zeros (the node with value 3).\n   - The list now looks like: `0 -> 4 -> 1 -> 0 -> 4 -> 5 -> 2 -> 0`\n\n5. Recursive call: `mergeNodes(ptr)`\n   - We recursively call `mergeNodes` with `ptr` pointing to the next zero (0).\n\n6. Fetch sum from current 0 to next 0:\n   - `ptr` is initialized to `head.next`, pointing to the first node after the second zero.\n   - `sum` is initialized to 0.\n   - We traverse the list using `ptr` until we reach the next zero.\n     - `ptr` points to 4, `sum` is updated to 4.\n     - `ptr` points to 5, `sum` is updated to 9.\n     - `ptr` points to 2, `sum` is updated to 11.\n     - `ptr` points to 0, we stop the loop since we found the next zero.\n\n7. Assign sum on the first node between nodes having value 0:\n   - We assign the value of `sum` (11) to the first node between the two zeros (the node with value 4).\n   - The list now looks like: `0 -> 4 -> 1 -> 0 -> 11 -> 0`\n\n8. Recursive call: `mergeNodes(ptr)`\n   - We recursively call `mergeNodes` with `ptr` pointing to the next zero (0).\n\n9. Base case: `head.next` is null, so we return `nullptr` (or `None` in Python).\n\n10. Return the modified list:\n    - The final modified list is: `0 -> 4 -> 1 -> 0 -> 11 -> 0`\n\nThe `mergeNodes` function returns the modified list starting from the second node, which becomes the new head of the list.\n\n---\n\n# Code\n```java []\nclass Solution {\n    public ListNode mergeNodes(ListNode head) {\n        // BASE CASE -> if we have a single zero, simply return null\n        if (head.next == null) return null;\n        \n        // fetch sum from current 0 to next 0\n        ListNode ptr = head.next;\n        int sum = 0;\n        while (ptr.val != 0) {\n            sum += ptr.val;\n            ptr = ptr.next;\n        }\n        \n        // assign sum on the first node between nodes having value 0\n        head.next.val = sum;\n        \n        // call and get the answer and connect the answer to next of head->next\n        head.next.next = mergeNodes(ptr);\n        \n        // return head->next..=> new head\n        return head.next;\n    }\n}\n```\n```python3 []\nclass Solution:\n    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        # BASE CASE -> if we have a single zero, simply return null\n        if not head.next:\n            return None\n        \n        # fetch sum from current 0 to next 0\n        ptr = head.next\n        sum = 0\n        while ptr.val != 0:\n            sum += ptr.val\n            ptr = ptr.next\n        \n        # assign sum on the first node between nodes having value 0\n        head.next.val = sum\n        \n        # call and get the answer and connect the answer to next of head->next\n        head.next.next = self.mergeNodes(ptr)\n        \n        # return head->next..=> new head\n        return head.next\n```\n```C++ []\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head){\n    //BASE CASE -> if we have a single zero, simply return null\n    if(!head->next) return nullptr;\n    \n    //fetch sum from current 0 to next 0\n    ListNode* ptr= head->next;\n    int sum=0;\n    while(ptr->val!=0) sum+= ptr->val, ptr=ptr->next;\n    \n    //assign sum on the first node between nodes having value 0.\n    head->next->val= sum;\n    \n    //call and get the answer and connect the answer to next of head->next\n    head->next->next= mergeNodes(ptr);\n    \n    //return head->next..=> new head\n    return head->next;\n}\n};\n```\n---\n![upvote.png](https://assets.leetcode.com/users/images/e6f4f26f-a7f5-465b-8ec1-aa665db072f9_1719537871.6475258.png)\n\n\n\n
['Linked List', 'Simulation', 'C++', 'Java', 'Python3']