Merge Nodes in Between Zeros - Beats 68.56% in Python
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires modifying a linked list by merging nodes between consecutive zeroe
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires modifying a linked list by merging nodes between consecutive zeroes into a single node whose value is the sum of all the nodes being merged. The resulting list should exclude all zeroes.\n\nThe key insight is to traverse the list, keep summing values between zeroes, and replace the starting zero\'s next node with the computed sum. This ensures that the new list is constructed as we traverse, excluding the zeroes.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialization:** Start with a dummy node that helps simplify edge cases and begin traversal from the node next to the head.\n2. **Traversal and Summation:**\n    - Iterate through the list and keep summing values until encountering a zero.\n    - Each time a zero is encountered (indicating the end of a segment), update the next node to hold the computed sum and skip to the next segment.\n3. **List Update:** After computing the sum for a segment, link the last node of the current segment to the first node of the next segment to exclude the zeroes.\n4. **Termination:** Ensure the new list is properly terminated by setting the next of the last node to null.\n\n# Complexity\n- **Time complexity:** O(n) where n is the number of nodes in the linked list. We traverse the list once.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity:** O(1) because we only use a few additional pointers and integer variables for summing, without extra data structures.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        # Initialize the current sum to 0\n        currSum = 0\n\n        # Traverse the list and point to the new merged nodes\n        flag = head\n\n        # Traverse the original list, starting from the first node after the head\n        temp = head.next\n\n        # Iterate through the list until \'temp\' reaches the end\n        while temp:\n            # Check if the current node\'s value is 0\n            if temp.val == 0:\n\n                # Create a new node with the current sum\n                node = ListNode(currSum)\n\n                # Link the \'flag\' node to this new node\n                flag.next = node\n\n                # Move the \'flag\' pointer to this new node\n                flag = node\n                \n                # Reset the current sum to 0 for the next segment\n                currSum = 0\n\n            else:\n                # If the current node\'s value is not 0, add it to the current sum\n                currSum += temp.val\n\n            # Move to the next node in the list\n            temp = temp.next\n\n        # Return the new list starting from the node after the initial head\n        return head.next\n```
['Python3']