[C++] 3 different solutions (Recursive & Iterative)
Solution 1: Iterative with extra space\nTime: O(N)\nSpace: O(N)\n\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        ListNode* sent
Solution 1: Iterative with extra space\nTime: O(N)\nSpace: O(N)\n```\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        ListNode* sentinel = new ListNode(-1);\n        ListNode* main = new ListNode(-1);\n        sentinel->next = main;\n        ListNode* cur = head->next;\n        \n        while (cur != nullptr) {\n            int sum = 0;\n            while (cur->val != 0) {\n                sum += cur->val;   \n                cur = cur->next;\n            }\n            main->val = sum;\n            cur = cur->next;\n            if (cur) {\n                main->next = new ListNode(-1);\n                main = main->next;\n            }  \n        }\n        \n        return sentinel->next;\n    }\n};\n```\n\nSolution 2: Iterative with no extra space\nTime: O(N)\nSpace: O(1)\n```\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        ListNode* sentinel = new ListNode(-1);;\n        sentinel->next = head;\n        ListNode* cur = head->next;\n        ListNode* zero = head;\n        \n        while (cur) {\n            int sum = 0;\n            while (cur->val != 0) {\n                sum += cur->val;   \n                cur = cur->next;\n            }\n            zero->val = sum;\n            if (cur->next)\n                zero->next = cur;\n            else\n                zero->next = nullptr;\n            zero = zero->next;\n            cur = cur->next; \n        }\n        \n        return sentinel->next;\n    }\n};\n```\n\nSolution 3: Recursive with no extra space\nTime: O(N)\nSpace: O(N) if we consider the recursion stack frame and O(1) without considering it \n```\nclass Solution {\npublic:\n    ListNode* mergeNodes(ListNode* head) {\n        head = head->next;\n        if (head == nullptr)\n            return head;\n        \n        int sum = 0;\n        ListNode* cur = head;\n        while (cur->val != 0) {\n            sum += cur->val;\n            cur = cur->next;\n        }\n        \n        head->val = sum;\n        head->next = mergeNodes(cur);\n        return head;\n    }\n};\n```
['Linked List', 'Recursion', 'C', 'Iterator']