[Linked List Two Solutions Tutorial] Merge Nodes in Between Zeros
Topic :  Linked List\nA linked list is a fundamental data structure in computer science. It consists of nodes where each node contains data and a reference (lin
**Topic** :  Linked List\nA linked list is a fundamental data structure in computer science. It consists of nodes where each node contains data and a reference (link) to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion operations compared to arrays. (GFG)\n\nThe crucial aspect to note about linked list:\n* For adding a new node or deleting an existing node, the operations in a linked list are `O(1)`.\n* To traverse the entire list, the time complexity in a linked list is `O(n)`.\n* It can also serve as a stack or a queue.\n\n___\n\n## Solution1\nTo traverse a linked list, we can employ the following straightforward pseudocode:\n```\nwhile(node != null) {\n\tprint(node);\n\tnode = node.next;\n}\n```\n\nWe begin traversing the linked list from the second node onward, as the first node always contains the value `0`. Simultaneously during our traversal, we calculate the accumulated sum for all non-zero nodes.\n\nOnce it reaches the next node with a value of 0, we simply create a new node with the accumulated sum value and add it to our new list.\n\n<br/>\n\n```c++ []\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        ListNode* dummy = new ListNode();\n        ListNode* cur = dummy;\n        head = head->next;\n        int sum = 0;\n        while (head != nullptr) {\n            if (head->val == 0) {\n                cur->next = new ListNode(sum);\n                cur = cur->next;\n                sum = 0;\n            }\n            sum += head->val;\n            head = head->next;\n        }\n        return dummy->next;\n    }\n};\n```\n```java []\nclass Solution {\n    public ListNode mergeNodes(ListNode head) {\n        ListNode dummy = new ListNode(), cur = dummy;\n        head = head.next;\n        int sum = 0;\n        while(head != null) {\n            if(head.val == 0) {\n                cur.next = new ListNode(sum);\n                cur = cur.next;\n                sum = 0;\n            } \n            sum += head.val;\n            head = head.next;\n        }\n        return dummy.next;\n    }\n}\n```\n```python []\nclass Solution:\n    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        dummy = ListNode()\n        cur = dummy\n        head = head.next\n        sum_val = 0\n        while head:\n            if head.val == 0:\n                cur.next = ListNode(sum_val)\n                cur = cur.next\n                sum_val = 0\n            sum_val += head.val\n            head = head.next\n        return dummy.next\n```\n```Go []\nfunc mergeNodes(head *ListNode) *ListNode {\n    dummy := &ListNode{}\n    cur := dummy\n    head = head.Next\n    sum := 0\n    for head != nil {\n        if head.Val == 0 {\n            cur.Next = &ListNode{Val: sum}\n            cur = cur.Next\n            sum = 0\n        }\n        sum += head.Val\n        head = head.Next\n    }\n    return dummy.Next\n}\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param ListNode $head\n     * @return ListNode\n     */\n    function mergeNodes($head) {\n        $dummy = new ListNode();\n        $cur = $dummy;\n        $head = $head->next;\n        $sum = 0;\n        while ($head != null) {\n            if ($head->val == 0) {\n                $cur->next = new ListNode($sum);\n                $cur = $cur->next;\n                $sum = 0;\n            }\n            $sum += $head->val;\n            $head = $head->next;\n        }\n        return $dummy->next;\n    }\n}\n```\n```javascript []\nvar mergeNodes = function(head) {\n    let dummy = new ListNode();\n    let cur = dummy;\n    head = head.next;\n    let sum = 0;\n    while (head !== null) {\n        if (head.val === 0) {\n            cur.next = new ListNode(sum);\n            cur = cur.next;\n            sum = 0;\n        }\n        sum += head.val;\n        head = head.next;\n    }\n    return dummy.next;    \n};\n```\n\n**Complexity**:\n* Time Complexity : `O(n)`\n* Space Complexity : `O(1)`\n\n## Solution2\nNote that when we encounter a node with a value of 0, we do not need to create a new node. Instead, we can directly assign the accumulated sum to the zero-node and append it to our new list.\n\n<br/>\n\n```c++ []\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        ListNode* dummy = new ListNode();\n        ListNode* cur = dummy;\n        head = head->next;\n        int sum = 0;\n        while (head != nullptr) {\n            if (head->val == 0) {\n                cur->next = head;\n                head -> val = sum;\n                cur = cur->next;\n                sum = 0;\n            } else {\n                sum += head->val;\n            }\n            head = head->next;\n        }\n        return dummy->next;\n    }\n};\n```\n```java []\nclass Solution {\n    public ListNode mergeNodes(ListNode head) {\n        ListNode dummy = new ListNode(), cur = dummy;\n        head = head.next;\n        int sum = 0;\n        while(head != null) {\n            if(head.val == 0) {\n                cur.next = head;\n                head.val = sum;\n                cur = cur.next;\n                sum = 0;\n            } else {\n                sum += head.val;\n            }\n            head = head.next;\n        }\n        return dummy.next;\n    }\n}\n```\n```python []\nclass Solution:\n    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:\n        dummy = ListNode()\n        cur = dummy\n        head = head.next\n        sum_val = 0\n        while head:\n            if head.val == 0:\n                cur.next = head\n                head.val = sum_val\n                cur = cur.next\n                sum_val = 0\n            else:\n                sum_val += head.val\n            head = head.next\n        return dummy.next\n```\n```Go []\nfunc mergeNodes(head *ListNode) *ListNode {\n    dummy := &ListNode{}\n    cur := dummy\n    head = head.Next\n    sum := 0\n    for head != nil {\n        if head.Val == 0 {\n            cur.Next = head\n            head.Val = sum\n            cur = cur.Next\n            sum = 0\n        } else {\n           sum += head.Val \n        }\n        head = head.Next\n    }\n    return dummy.Next\n}\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param ListNode $head\n     * @return ListNode\n     */\n    function mergeNodes($head) {\n        $dummy = new ListNode();\n        $cur = $dummy;\n        $head = $head->next;\n        $sum = 0;\n        while ($head != null) {\n            if ($head->val == 0) {\n                $cur->next = $head;\n                $head->val = $sum;\n                $cur = $cur->next;\n                $sum = 0;\n            } else {\n               $sum += $head->val; \n            }\n            $head = $head->next;\n        }\n        return $dummy->next;\n    }\n}\n```\n```javascript []\nvar mergeNodes = function(head) {\n    let dummy = new ListNode();\n    let cur = dummy;\n    head = head.next;\n    let sum = 0;\n    while (head !== null) {\n        if (head.val === 0) {\n            cur.next = head;\n            head.val = sum;\n            cur = cur.next;\n            sum = 0;\n        } else {\n            sum += head.val;\n        }\n        head = head.next;\n    }\n    return dummy.next;    \n};\n```\n\n**Complexity**:\n* Time Complexity : `O(n)`\n* Space Complexity : `O(1)`\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['PHP', 'Python', 'Java', 'Go', 'JavaScript']