430: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Define the function flattenDFS which takes a Node object as input and 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Define the function flattenDFS which takes a Node object as input and returns a Node object.\n2. Check if the node object is None. If it is, return None.\n3. Check if node object has no child and no next pointers. If it does not, return the node object.\n4. Check if the node object has no child pointer. If it does not, call flattenDFS with the next node and return its result.\n5. Call flattenDFS with the child node and store its result in childTail.\n6. Get the next node of node and store it in nextNode.\n7. If nextNode is not None, set childTail.next to nextNode and set nextNode.prev to childTail.\n8. Set node.next to node.child and set node.child.prev to node.\n9. Set node.child to None.\n10. Call flattenDFS with nextNode if it is not None, otherwise call it with childTail. Store the result in a variable.\n11. Return the head of the flattened linked list after calling flattenDFS with the input head and completing the process.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def flatten(self, head: \'Node\') -> \'Node\':\n        def flattenDFS(node):\n            if not node:\n                return None\n            if not node.child and not node.next:\n                return node\n            if not node.child:\n                return flattenDFS(node.next)\n            childTail = flattenDFS(node.child)\n            nextNode = node.next\n            if nextNode:\n                childTail.next = nextNode\n                nextNode.prev = childTail\n            node.next = node.child\n            node.child.prev = node\n            node.child = None\n            return flattenDFS(nextNode) if nextNode else childTail\n        flattenDFS(head)\n        return head\n\n```
['Linked List', 'Depth-First Search', 'Doubly-Linked List', 'Python', 'Python3']