✅ [C++] | Beginner Friendly | Two Solutions DFS & Iterative | O(1)
Complexity\n- Time complexity: O(n)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n)\n Add your space complexity here, e.g. O(n) \n\n## D
## Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n## DFS\n```\nclass Solution {\npublic:\n    vector<Node*> nodes;\n    void dfs(Node* head) {\n        if(!head) return;\n        nodes.push_back(head);\n        if(head->child) dfs(head->child);\n        dfs(head->next);\n    }\n\n    Node* flatten(Node* head) {\n        dfs(head);\n        for(auto x : nodes) cout << x -> val << " ";\n\n        int n = nodes.size();\n        if(n == 0) return nullptr;\n\n        for(int i = 0; i < n - 1; i++) {nodes[i]->next = nodes[i+1]; nodes[i] -> child = nullptr;}\n        for(int i = n -1 ; i > 0; i--) {nodes[i]->prev = nodes[i-1]; nodes[i] -> child = nullptr;}\n        nodes[0] -> prev = nullptr;\n        nodes[n - 1] -> next = nullptr;\n\n        return nodes[0];\n    }\n};\n\n```\n## Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n## Iterative Method\n```\n/*\nclass Solution {\npublic:\n    Node* flatten(Node* head) {\n        for(Node* h = head; h != nullptr; h = h -> next) {\n            if(h -> child) {\n                Node* next = h -> next;\n                h->next = h->child;\n                h->child->prev = h;\n                h->child = nullptr;\n\n                Node* p = h -> next;\n                while(p -> next) p = p -> next;\n                p -> next = next;\n                if(next) next -> prev = p; \n            }\n        }\n\n        return head;\n    }\n};\n```
['C++']