1 pass with 2 pointers-> without memory leaks||4ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nLearn Linked list from the old school.\n2  pointers solution for Java, C++ & Python.\n\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLearn Linked list from the old school.\n2  pointers solution for Java, C++ & Python.\n\n2nd C++ is considering to remove the problem caused by memory leakage.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. 2 pointers `prev` & `curr` pointing to `head->next`\n2. Create a linked list `ans(0, curr)` with a dummy node.\n3. Use a loop while `curr!=NULL` with step `curr=curr->next` do:\n```\nx=curr->val;\nif (x!=0) sum+=x;\nelse{\n    prev->val=sum;\n    prev->next=curr->next;\n    prev=prev->next;\n    sum=0;\n}\n```\n4. `ans.next` is the answer\n5.  Code without memory leaks is also implemented, but the price is  slowing down the speed.\n6. Draw a picture is the best way to learn the linked list; considering  `curr->val==0`\n![LC2181.png](https://assets.leetcode.com/users/images/e3c7349e-1ad7-46d4-a1d5-35114b26f7a4_1720057224.3950033.png)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Code ||Java 4ms Beats 100% |C++341ms Beats 99.66%\n```Java []\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     int val;\n *     ListNode next;\n *     ListNode() {}\n *     ListNode(int val) { this.val = val; }\n *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n * }\n */\nclass Solution {\n    public ListNode mergeNodes(ListNode head) {\n        ListNode prev=head.next, curr=head.next;\n        int sum=0;\n        for (; curr!=null; curr=curr.next){\n            int x=curr.val;\n            if (x!=0) sum+=x;\n            else{\n                prev.val=sum;\n                prev.next=curr.next;\n                prev=prev.next;\n                sum=0;\n            }\n        } \n        return head.next;\n    }\n}\n```\n```C++ []\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* prev=head->next, *curr=head->next;\n        ListNode ans(0, curr);\n        int sum=0;\n        for (; curr; curr=curr->next){\n            int x=curr->val;\n            if (x!=0) sum+=x;\n            else{\n                prev->val=sum;\n                prev->next=curr->next;\n                prev=prev->next;\n                sum=0;\n            }\n        } \n        return ans.next;\n    }\n};\n\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n```Python []\n# Definition for singly-linked list.\n# class ListNode:\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution:\n    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        prev, curr=head.next, head.next\n        sum=0\n        while curr:\n            x=curr.val\n            if x!=0: sum+=x\n            else:\n                prev.val=sum\n                prev.next=curr.next\n                prev=prev.next\n                sum=0\n            curr=curr.next\n        return head.next\n        \n```\n# C++ code without memory leaks||411ms Beats 83.79%\nOne needs an extra pointer `tmp` for freeing the node. The node ` curr` with `prev==curr` cannot be free.\n```\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        ListNode* prev=head->next, *curr=head->next, *tmp=head;\n        delete tmp;// delete tmp\n        ListNode ans(0, curr);\n        int sum=0;\n        for (; curr; curr=curr->next, delete tmp){ //delete tmp\n            int x=curr->val;\n            if (x!=0) {\n                sum+=x;\n                // if prev==curr cannot be deleted\n                tmp=(prev==curr)?NULL:curr;\n            }\n            else{\n                tmp=curr;\n                prev->val=sum;\n                prev->next=curr->next;\n                prev=prev->next;\n                sum=0;\n            }\n        } \n        return ans.next;\n    }\n};\n```\nLinked list may encounter the problem of memory leaks. Solving the 2 pointers related question [19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/solutions/4813267/fast-slow-pointers-care-with-memory-leaks-0ms-beats-100/), the C, C++ codes without memory leaks are also provided.\n[Please Turn on English subtitles if necessary]\n[https://youtu.be/OqLR3ShDALY?si=b7OH-IeA7fvr5BJE](https://youtu.be/OqLR3ShDALY?si=b7OH-IeA7fvr5BJE)
['Linked List', 'Two Pointers', 'Simulation', 'C++', 'Java', 'Python3']