C++ | Simple Recursion
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can iterate through our linked list while adding Child Lists in between after flatte
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can iterate through our linked list while adding **Child Lists** in between after flattening them using simple Recursion.\n\n# Approach\nWhenever in our list, if we found a node with child list:\n1) Save the **next** node\n2) Flatten the child list using **recursion**\n3) Patch the list in between **current** and **next** node.\n\n# Complexity\n- Time complexity: O(n) (Each node visited once)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1) (Constant extra space used)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    Node* flatten(Node* head) {\n        Node* itr1 = head;\n        while(itr1){\n            if(itr1->child){\n                Node* itr2 = flatten(itr1->child);\n                Node* next = itr1->next;\n                // Add child-list next to current node\n                patch(itr1, itr2); \n                while(itr2->next) itr2 = itr2->next;\n                // Add \'next\' node after last element of child list\n                patch(itr2, next);\n                itr1->child = NULL;\n                itr1 = next;\n            }\n            else itr1 = itr1->next;\n        }\n        return head;\n    }\n\n    void patch(Node* node1, Node* node2){\n        if(node1) node1->next = node2;\n        if(node2) node2->prev = node1;\n    }\n};\n```\nHope you will find it helpful...\n```
['Recursion', 'C++']