0 ms | 100% beat Solution | C++ | Very Easy Approach
Approach\n Describe your approach to solving the problem. \n1. Traverse the list while handling child pointers:\n    - Iterate through the list nodes.\n    - If
# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Traverse the list while handling child pointers:\n    - Iterate through the list nodes.\n    - If a node has a `child`, update the `next` and `child` pointers accordingly.\n    - Collect the next node after the current level in a vector `nodes` (stack can also be used) for later connection.\n\n1. Reverse Process Child Nodes:\n    - Reverse the `nodes` vector to traverse child nodes in the correct order.\n    - `next` pointer always indicate last node at end of each iteration. So that you can attach the next list\'s head to previous one\'s end\n    - Connect each child node to its parent node.\n\n# 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# Code\n```\nclass Solution {\npublic:\n    Node* flatten(Node* head) {\n        Node* curr = head;  // Initialize the current node to the head of the list\n        Node* next;\n        vector<Node*> nodes;  // To keep track of nodes with child lists or you could use stack\n\n        // Traverse through the list\n        while (curr) {\n            Node* it = curr;\n\n            // Traverse to the end of the current level without a child\n            while (it->child == NULL && it->next != NULL) {\n                it = it->next;\n            }\n\n            Node* forward = it->next;  // Store the next node at this level\n            nodes.push_back(forward);  // Store it for future processing\n\n            Node* ch = it->child;  // Get the child node if it exists\n            it->next = ch;  // Connect the child as the next node at this level\n            it->child = NULL;  // Set child pointer to NULL\n\n            if (ch)\n                ch->prev = it;  // Update the previous pointer of the child\n\n            next = it;  // Update the \'next\' pointer to the last node at this level\n            curr = ch;  // Move the current pointer to the start of the child list\n        }\n\n        reverse(nodes.begin(), nodes.end());  // Reverse the vector to process nodes in reverse order (see the examples)\n\n        // Connect child nodes after their parent node\n        for (auto node : nodes) {\n            Node* temp = node;\n\n            if (temp) {\n                next->next = node;  // Connect the parent node to the child node\n                node->prev = next;  // Update the previous pointer of the child node\n\n                // Traverse to the end of the child list\n                while (temp->next != NULL) {\n                    temp = temp->next;\n                }\n                next = temp;  // Update \'next\' pointer to the last node in the child list\n            }\n        }\n\n        return head;  // Return the head of the flattened list\n    }\n};\n\n```\nPlease upvote if you liked the solution :)
['Linked List', 'Stack', 'Depth-First Search', 'Doubly-Linked List', 'C++']