✅Beats 100% -Explained with [ Video ] -C++/Java/Python/JS - Single Pass - O(N)
\n\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n *
![Screenshot 2024-07-04 055119.png](https://assets.leetcode.com/users/images/7874260e-7ded-4903-a632-0c784811881e_1720053043.8851676.png)\n\n\n# YouTube Video Explanation:\n\n### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail.\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n\nhttps://youtu.be/5mQjCgtYT58\n\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2600 Subscribers*\n*Current Subscribers: 2504*\n\nFollow me on Instagram : https://www.instagram.com/divyansh.nishad/\n\n---\n\n\n# 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**:\n   - 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**:\n   - 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- **Space Complexity**: O(1) because we only use a few additional pointers and integer variables for summing, without extra data structures.\n\n# Step by Step Explanation\n\nThe linked list we start with: `0 -> 3 -> 1 -> 0 -> 4 -> 5 -> 2 -> 0`\n\n| Step | Current Node | Action | Sum | Modified List | Next Node |\n|------|---------------|--------|-----|----------------|-----------|\n| 1    | 0             | Initialize pointers | 0   |  | 3 |\n| 2    | 3             | Add to sum | 3   |  | 1 |\n| 3    | 1             | Add to sum | 4   |  | 0 |\n| 4    | 0             | Create new node with sum | 4   | 4 | 4 |\n| 5    | 4             | Add to sum | 4   | 4 | 5 |\n| 6    | 5             | Add to sum | 9   | 4 | 2 |\n| 7    | 2             | Add to sum | 11  | 4 | 0 |\n| 8    | 0             | Create new node with sum | 11  | 4 -> 11 | null |\n| 9    | null          | End |  | 4 -> 11 |  |\n\n#### Steps\n1. **Step 1**: Initialize pointers. We skip the initial 0 and start from the next node (3). Set `modify` and `nextSum` to this node.\n2. **Step 2 & 3**: Traverse nodes and accumulate the sum until the next 0 is encountered. For nodes 3 and 1, sum becomes 4.\n3. **Step 4**: When a 0 is encountered, create a new node with the accumulated sum (4). Move `modify` and `nextSum` pointers to the next non-zero node (4).\n4. **Step 5, 6 & 7**: Repeat the process for the next block. Traverse nodes 4, 5, and 2, accumulating their sum to 11.\n5. **Step 8**: When the next 0 is encountered, create a new node with the sum (11). As there are no more nodes, the process ends.\n6. **Step 9**: The resulting modified list is `[4, 11]`.\n\n\n# Code\n```java []\npublic class Solution {\n\n    public ListNode mergeNodes(ListNode head) {\n        // Initialize a sentinel/dummy node with the first non-zero value.\n        ListNode modify = head.next;\n        ListNode nextSum = modify;\n\n        while (nextSum != null) {\n            int sum = 0;\n            // Find the sum of all nodes until you encounter a 0.\n            while (nextSum.val != 0) {\n                sum += nextSum.val;\n                nextSum = nextSum.next;\n            }\n\n            // Assign the sum to the current node\'s value.\n            modify.val = sum;\n            // Move nextSum to the first non-zero value of the next block.\n            nextSum = nextSum.next;\n            // Move modify also to this node.\n            modify.next = nextSum;\n            modify = modify.next;\n        }\n        return head.next;\n    }\n}\n```\n```C++ []\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* modify = head->next; // Start from the node after the initial 0\n        ListNode* nextSum = modify;\n\n        while (nextSum != nullptr) {\n            int sum = 0;\n            // Find the sum of all nodes until you encounter a 0.\n            while (nextSum->val != 0) {\n                sum += nextSum->val;\n                nextSum = nextSum->next;\n            }\n\n            // Assign the sum to the current node\'s value.\n            modify->val = sum;\n            // Move nextSum to the first non-zero value of the next block.\n            nextSum = nextSum->next;\n            // Move modify also to this node.\n            modify->next = nextSum;\n            modify = modify->next;\n        }\n        return head->next; // Skip the initial 0 node.\n    }\n};\n```\n```Python []\n# Definition for singly-linked list.\n# class ListNode(object):\n#     def __init__(self, val=0, next=None):\n#         self.val = val\n#         self.next = next\nclass Solution(object):\n    def mergeNodes(self, head):\n        modify = head.next  # Start from the node after the initial 0\n        next_sum = modify\n\n        while next_sum:\n            total = 0\n            # Find the sum of all nodes until you encounter a 0.\n            while next_sum.val != 0:\n                total += next_sum.val\n                next_sum = next_sum.next\n\n            # Assign the sum to the current node\'s value.\n            modify.val = total\n            # Move next_sum to the first non-zero value of the next block.\n            next_sum = next_sum.next\n            # Move modify also to this node.\n            modify.next = next_sum\n            modify = modify.next\n\n        return head.next  # Skip the initial 0 node\n        \n```\n```JavaScript []\n/**\n * Definition for singly-linked list.\n * function ListNode(val, next) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.next = (next===undefined ? null : next)\n * }\n */\n/**\n * @param {ListNode} head\n * @return {ListNode}\n */\nvar mergeNodes = function(head) {\n    let modify = head.next; // Start from the node after the initial 0\n    let nextSum = modify;\n\n    while (nextSum !== null) {\n        let sum = 0;\n        // Find the sum of all nodes until you encounter a 0.\n        while (nextSum.val !== 0) {\n            sum += nextSum.val;\n            nextSum = nextSum.next;\n        }\n\n        // Assign the sum to the current node\'s value.\n        modify.val = sum;\n        // Move nextSum to the first non-zero value of the next block.\n        nextSum = nextSum.next;\n        // Move modify also to this node.\n        modify.next = nextSum;\n        modify = modify.next;\n    }\n    return head.next; // Skip the initial 0 node\n};\n```\n\n![upvote.png](https://assets.leetcode.com/users/images/c9cd1665-11f0-44f6-bb5b-524d500b9bed_1720053024.5832372.png)\n
['Linked List', 'Simulation', 'Python', 'C++', 'Java', 'JavaScript']