C++ solution with explanation
Original solution: https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/discuss/152066/c%2B%2B-about-10-lines-solution\nI will try to explain t
Original solution: https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/discuss/152066/c%2B%2B-about-10-lines-solution\nI will try to explain the logic behind the code. Here we are iterating though our doubly linked list, if the current node does not have a child, go on. If it does, we first store the next node in a temporary variable next, as we will change the next pointer of the current node to its child. Then do the same, change next pointer of current node to child, prev pointer of child (now next) node to current node and child pointer of current node to NULL. Now store the next pointer of current node in another temporary variable tmp. We need a temporary variable, as we will be iterating through it and we already have a loop going on for h, and hence, cant iterate through it. Iterate until we have next pointer to a tmp node. Once tmp reach the last node in that level, assign its next pointer to previosuly stored next pointer and if next does exist, assign its prev pointer to tmp. \nLogic is simple, as we try to flatten 1 layer at a time, kinda like BFS. Note that we have a inner while loop that accomodates all the nodes in the child level of the current node and assigns next pointer of the last node in child level to the current nodes next --> that\'s what we wanted. But what if some node in child level has a child? That will be handled in our for loop as now the next pointer to curent node is child itself, so every node in the child level will be checked for this condition further in the for loop. Same case for their child and same their child of child and so on.\n\n```\n/*\n// Definition for a Node.\nclass Node {\npublic:\n    int val;\n    Node* prev;\n    Node* next;\n    Node* child;\n};\n*/\n\nclass Solution {\npublic:\n    Node* flatten(Node* head) {\n        for(Node* h = head; h!=NULL; h = h->next)\n        {\n            if(h->child)\n            {\n                Node* next = h->next;\n                h->next = h->child;\n                h->next->prev = h;\n                h->child= NULL;\n                Node* tmp = h->next;\n                while(tmp->next)\n                    tmp=tmp->next;\n                tmp->next = next;\n                if(next)\n                    next->prev = tmp;\n            }\n        }\n        return head;\n    }\n};\n```\nTime complexity: O(N)\nSpace complexity: O(1)
['C', 'Iterator', 'C++']