Implementation using stack and dummy pointer [99% Space Complexity]
Intuition\n Describe your first thoughts on how to solve this problem. \nMy First thoughts upon viewing the questions is to some how save the head.next nodes wh
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMy First thoughts upon viewing the questions is to some how save the `head.next` nodes when encountering the nodes with the `head.child` nodes. As saving the `head.next` once we continue moving forward in the child node and reach the end I can pop the stack, make curent node.next to the pop and pop.prev to current and can finish the problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. The `end` list is used to keep track of nodes next to the nodes with children that need to be reconnected after flattening. `res` is used to store the original head of the linked list, and it will be returned as the result.\n\n2. The solution enters a while loop that iterates through the linked list, starting with the `head`.\n\n3. Inside the loop, it checks if the current node has a child (the `child` attribute is not None). If it does have a child, it performs the following steps:\n   - If the current node also has a next node (`head.next` is not None), it pushes the next node onto the `end` stack for later reconnection.\n   - It updates the `head.next` to point to the child node and sets the child node\'s `prev` pointer to the current `head`.\n   - Finally, it sets the current node\'s `child` attribute to None, effectively detaching the child.\n\n4. The solution then checks if the current node has reached the end of the list (`head.next` is None) and if there are nodes in the `end` stack waiting to be reconnected. If both conditions are met, it pops a node (`no`) from the `end` stack, and if `no` is not None, it reconnects it to the current node as the next node, and updates the `prev` pointer accordingly.\n\n5. The `head` pointer is then moved to the next node in the original list, and the loop continues until it reaches the end of the list.\n\n6. Finally, the `res` (original head) is returned as the flattened doubly linked list.\n\nThis approach effectively flattens a multilevel doubly linked list while maintaining the original order of nodes. It uses a stack (`end`) to keep track of nodes next to the nodes with children, and it modifies the pointers accordingly to achieve the desired result.\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(n)$$\n<small>In only the wort case scenario it will be $$O(n)$$, which is the case where every node has a child. Excluding that every other case will have much better time complexity.</small>\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n"""\n# Definition for a Node.\nclass Node:\n    def __init__(self, val, prev, next, child):\n        self.val = val\n        self.prev = prev\n        self.next = next\n        self.child = child\n"""\n\nclass Solution:\n    def flatten(self, head: \'Optional[Node]\') -> \'Optional[Node]\':\n        if not head:\n            return None\n\n        end = []\n        res = head\n        while head:\n            if head.child:\n                if head.next:\n                    end.append(head.next)\n                head.next = head.child\n                head.next.prev = head\n                head.child=None\n            if not head.next and end:\n                no = end.pop() if end else None\n                if no :\n                    head.next = no\n                    no.prev = head\n            head = head.next\n\n        return res\n```
['Two Pointers', 'Stack', 'Python3']