✅ Recursive vs Iterative without Dummy || O(1) Space + Intuition
For these modification Questions , Recursion is a great tool in these linked list question.\n\nMy Intuition :\nWhenever the process is having repeated tasks aga
For these modification Questions , **Recursion** is a great tool in these linked list question.\n\n**My Intuition** :\nWhenever `the process is having repeated tasks again and again especially in Linked List`, We use **Recursion**.\n# For eg -> \n```\n1. Skip M nodes, delete N nodes nodes\n2. Reverse every K nodes.\n3. Skip M node, Reverse N nodes.\n4. get sum between consecutive 0\'s.{This Question}.\n```\n\nYou see all above question are having **same tasks again and again**, and thats why **I thought of Recursion**.\n              \n\n**Algorithm**: In Recursion , we only have to consider about first part and rest will be done by principle of recursion.\n1. Fetch the sum between two consecutive 0.\n2. Assign the sum to first node between 2 consecutive 0\'s.\n3. Call function for the next parts.\n4. Whatever was returned from the function , assign it to next of the first node on which we assigned the sum previously.\n5. Return the New head as head->next.\n\n**We are using Constant space because we are not creating any extra node for sum.**\n**We are just assigning the sum to already existed node.**\n# C++ Recursive : Very Easy\n    ListNode* mergeNodes(ListNode* head){\n\t    //BASE CASE -> if we have a single zero, simply return null\n        if(!head->next) return nullptr;\n        \n        //fetch sum from current 0 to next 0\n        ListNode* ptr= head->next;\n        int sum=0;\n        while(ptr->val!=0) sum+= ptr->val, ptr=ptr->next;\n        \n        //assign sum on the first node between nodes having value 0.\n        head->next->val= sum;\n        \n        //call and get the answer and connect the answer to next of head->next\n        head->next->next= mergeNodes(ptr);\n        \n        //return head->next..=> new head\n        return head->next;\n    }\n**Time**: O(N).\n**Space**: O(1) {Excluding recursion space}.\n\n\t\n# C++ Iterative :\tFaster than 95%\nSame as Recursive above but in iterative version.\nDoing everything INPLACE without creating new node for sum, as in recursion.\n   \n     ListNode* mergeNodes(ListNode* head) {\n         head=head->next;\n         ListNode* start=head;\n         while(start){\n\t\t    ListNode* end= start;   /* Point to first node of current part for getting sum */\n            int sum=0;\n            while(end->val!=0) sum+= end->val , end=end->next;\n            start->val=sum;   /*assign sum to first node between two 0*/\n            start->next=end->next;   /*make this connect to first node of next part*/\n            start=start->next;    /*go..to..next..part*/\n\t\t }\n         return head;\n    }\n\n**Time** -> O(N)\n**Space** -> O(1) {We are doing everything **inplace**, **without creating new nodes for sum**}\n\n\n
['C']