C++ Recursive and Iterative
The recursive idea is simple: each time when we reach a node with child, recursively flatten the child and insert it between the current node and its next node.
The recursive idea is simple: each time when we reach a node with `child`, recursively flatten the child and insert it between the current node and its next node. Remember to take care of the `prev` pointers.\n\n```cpp\nclass Solution {\npublic:\n    Node* flatten(Node* head) {\n        Node* cur = head;\n        while (cur) {\n            if (cur -> child) {\n                Node* next = cur -> next;\n                Node* child = flatten(cur -> child);\n                cur -> child = NULL;\n                cur -> next = child;\n                child -> prev = cur;\n                while (cur -> next) {\n                    cur = cur -> next;\n                }\n                cur -> next = next;\n                if (next) {\n                    next -> prev = cur;\n                }\n            }\n            cur = cur -> next;\n        }\n        return head;\n    }\n};\n```\n\nThe iterative one is: each time when we see a node with `child`, find the tail node in the `child` level and connect it with the `next` node of the current node. Then make the `child` node the `next` node and move on.\n\n```cpp\nclass Solution {\npublic:\n    Node* flatten(Node* head) {\n        Node* cur = head;\n        while (cur) {\n            if (cur -> child) {\n                Node* next = cur -> next;\n                cur -> next = cur -> child;\n                cur -> next -> prev = cur;\n                cur -> child = NULL;\n                Node* tail = cur -> next;\n                while (tail -> next) {\n                    tail = tail -> next;\n                }\n                tail -> next = next;\n                if (next) {\n                    next -> prev = tail;\n                }\n            }\n            cur = cur -> next;\n        }\n        return head;\n    }\n};\n```
[]