Flatten a Multilevel Doubly Linked List | c++ recursive/recursion SOLUTION | 8ms
\nclass Solution {\npublic:\n    // THINK OF THE PROBLEM AS NODES AS ROOMS PRESENT IN DIFFERENT DEPTHS/LEVELS OF AN\n    // HIGH RISE BUILDING\n    // Naturally
```\nclass Solution {\npublic:\n    // THINK OF THE PROBLEM AS NODES AS ROOMS PRESENT IN DIFFERENT DEPTHS/LEVELS OF AN\n    // HIGH RISE BUILDING\n    // Naturally we need to traverse the list, and hence we do that\n    // Whenever we encounter any child node, we recursively go to the depth and make\n    // changes to required links, and then call the function for the upcoming nodes\n    // present in that level.\n    \n    // Below is the step by step breakdown of the problem in my intuition\n    Node* solve(Node* head){\n        // base case\n        // first checking if either list is empty or we have reached a dead end\n        // dead end = child and next both point to NULL\n        if( head==NULL || (head->child==NULL && head->next==NULL)) return head;\n        \n        \n        // storing the next, for the time being because if we go deeper into the child nodes\n        // next may get lost\n        Node* t = head->next;\n        Node* n = NULL;\n        \n        // if child exists we go deeper into the list, and alongside change the links\n        // as required\n        if(head->child!=NULL){\n            \n            // connecting head\'s child to the next position and vice versa\n            // and making head\'s child NULL\n            Node* temp = head->child;\n            head->next = temp;\n            temp->prev = head;\n            head->child = NULL;\n            \n            // this returns a value where we have either got NULL or reached a dead end\n            n = solve(temp);\n            \n            // if we have reached a dead end for a particular level and above that level the\n            // list still has its nodes then we link them.\n            if(t!=NULL && n!=NULL){\n                n->next = t;\n                t->prev = n;\n            }\n        }\n        \n        // after making required connections on the previous node\'s child branches, we\n        // call it for the next nodes in that level\n        if(t!=NULL)\n            return solve(t);\n        \n        // if no next nodes are present on that level, that means we need the last node\n        // of the last level of our succeeding levels, and hence we return it.\n        return n;\n        \n    }\n    Node* flatten(Node* head) {\n        solve(head);\n        return head;\n    }\n};\n```
['Linked List', 'Recursion']