😎Brute Force to Efficient Method 100% beat🤩 | Java | C++
1st Method :- Brute force\n>The brute-force approach involves using recursion to traverse the nested doubly linked list and flatten it. Here\'s how you can do i
# 1st Method :- Brute force\n>The brute-force approach involves using recursion to traverse the nested doubly linked list and flatten it. Here\'s how you can do it step by step:\n\n1. Start at the head of the doubly linked list.\n2. Initialize a helper recursive function that takes a node as an argument.\n3. In the helper function:\n    - Check if the current node has a child (sub-list).\n    - If it does, recursively call the helper function on the child node to flatten it.\n    - After flattening the child list, connect the current node\'s `next` pointer to the flattened child\'s head.\n    - Update the child\'s `prev` pointer to point back to the current node.\n    - Set the current node\'s `child` pointer to null to remove the child link\n4. Continue this process for each node in the doubly linked list\n\n\n# Code\n``` Java []\nclass Solution {\n\n    public Node flatten(Node head) {\n        if (head == null) {\n            return null;\n        }\n        \n        // Helper function to flatten a node and its children\n        flattenNode(head);\n        \n        return head;\n    }\n\n    private Node flattenNode(Node node) {\n        Node current = node;\n        Node tail = node; // To keep track of the tail of the flattened list\n        \n        while (current != null) {\n            if (current.child != null) {\n                Node child = current.child;\n                current.child = null;\n                \n                // Flatten the child list and get the child list\'s tail\n                Node childTail = flattenNode(child);\n                \n                // Connect the current node to the flattened child\n                childTail.next = current.next;\n                if (current.next != null) {\n                    current.next.prev = childTail;\n                }\n                current.next = child;\n                child.prev = current;\n                \n                // Update the tail to be the tail of the merged list\n                tail = childTail;\n            }\n            \n            // Move to the next node in the original list\n            current = current.next;\n            if (current != null) {\n                tail = current; // Update the tail for non-null current nodes\n            }\n        }\n        \n        return tail; // Return the tail of the merged list\n    }\n}\n```\n``` C++ []\n\nclass Solution {\npublic:\n    Node* flatten(Node* head) {\n        if (head == nullptr) {\n            return nullptr;\n        }\n\n        // Helper function to flatten a node and its children\n        flattenNode(head);\n\n        return head;\n    }\n\nprivate:\n    Node* flattenNode(Node* node) {\n        Node* current = node;\n        Node* tail = node; // To keep track of the tail of the flattened list\n\n        while (current != nullptr) {\n            if (current->child != nullptr) {\n                Node* child = current->child;\n                current->child = nullptr;\n\n                // Flatten the child list and get the child list\'s tail\n                Node* childTail = flattenNode(child);\n\n                // Connect the current node to the flattened child\n                childTail->next = current->next;\n                if (current->next != nullptr) {\n                    current->next->prev = childTail;\n                }\n                current->next = child;\n                child->prev = current;\n\n                // Update the tail to be the tail of the merged list\n                tail = childTail;\n            }\n\n            // Move to the next node in the original list\n            current = current->next;\n            if (current != nullptr) {\n                tail = current; // Update the tail for non-null current nodes\n            }\n        }\n\n        return tail; // Return the tail of the merged list\n    }\n};\n```\n\n\n\n\n\n# Complexity\n#### Time complexity: O(N) ;\n- The time complexity of the brute-force approach is O(N), where N is the total number of nodes in the doubly linked list. This is because we visit each node exactly once while flattening the list.\n#### Space complexity: O(n) ; \n- The space complexity of the brute-force approach is O(H), where H is the maximum depth of the nested structure. This is because the recursion depth is bounded by the depth of the nested lists. In the worst case, when the list is completely nested, H can be equal to N (the total number of nodes), leading to a space complexity of O(N).\n\n> This brute-force approach recursively flattens the nested doubly linked list. However, it can be inefficient for large input lists with deep nesting because of the recursion overhead.\n\n# 2nd Method :- Efficient Method\n>To optimize the solution, we can use an iterative approach without recursion. Here\'s the step-by-step explanation:\n\n1. Start at the head of the doubly linked list.\n2. Use a stack to keep track of nodes with potential child lists.\n3. While traversing the list:\n    - If the current node has a child (sub-list):\n        - Save the next node in the main list.\n        - Connect the current node to the child list.\n        - Push the next node onto the stack for later processing.\n        - Update the current node to be the child list\'s last node.\n    - If the current node does not have a child and there are nodes in the stack, pop a node from the stack and connect it to the current node.\n4. Continue this process until you have processed all nodes in the list.\n\n``` Java []\nclass Solution {\n\n    public Node flatten(Node head) {\n        if (head == null) {\n            return null;\n        }\n        \n        Node current = head;\n        Stack<Node> stack = new Stack<>();\n        \n        while (current != null) {\n            if (current.child != null) {\n                Node nextNode = current.next;\n                \n                // Connect current node to the child list\n                current.next = current.child;\n                current.child.prev = current;\n                current.child = null;\n                \n                // Push the next node onto the stack for later processing\n                if (nextNode != null) {\n                    stack.push(nextNode);\n                }\n            } else if (current.next == null && !stack.isEmpty()) {\n                // If there are no more nodes in the current level,\n                // pop a node from the stack and connect it to the current node\n                Node nextNode = stack.pop();\n                current.next = nextNode;\n                nextNode.prev = current;\n            }\n            \n            current = current.next;\n        }\n        \n        return head;\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    Node* flatten(Node* head) {\n        if (head == nullptr) {\n            return nullptr;\n        }\n\n        Node* current = head;\n        stack<Node*> nodeStack;\n\n        while (current != nullptr) {\n            if (current->child != nullptr) {\n                Node* nextNode = current->next;\n\n                // Connect current node to the child list\n                current->next = current->child;\n                current->child->prev = current;\n                current->child = nullptr;\n\n                // Push the next node onto the stack for later processing\n                if (nextNode != nullptr) {\n                    nodeStack.push(nextNode);\n                }\n            } else if (current->next == nullptr && !nodeStack.empty()) {\n                // If there are no more nodes in the current level,\n                // pop a node from the stack and connect it to the current node\n                Node* nextNode = nodeStack.top();\n                nodeStack.pop();\n                current->next = nextNode;\n                nextNode->prev = current;\n            }\n\n            current = current->next;\n        }\n\n        return head;\n    }\n};\n```\n\nThis efficient approach uses an iterative process with a stack to flatten the nested doubly linked list, avoiding the overhead of recursion and making it more suitable for large input lists.\n\n\n# Complexity\n#### Time complexity: O(N) ;\n- The time complexity of the efficient approach is also O(N), where N is the total number of nodes in the doubly linked list. This is because we traverse each node in the list exactly once.\n#### Space complexity: O(1) ;\n- The space complexity of the efficient approach is O(1) because we use a constant amount of extra space, mainly for variables like current, stack, and temporary pointers. The space used is independent of the input size and does not depend on the depth of nesting. Therefore, it is a constant space algorithm.\n
['Stack', 'C++', 'Java']