Python Recursive Solution + Analysis
The key idea is to recursively flatten sublists, given the head. Flattening a child sublist and flattening a tail (contents of head.next) sublist is the same pr
The key idea is to recursively flatten sublists, given the head. Flattening a child sublist and flattening a tail (contents of head.next) sublist is the same procedure. Once we\'ve made the recursive calls, we need to assemble the list so that it\'s of the form head->[result of child flattening]->[result of tail flattening].\n\n## Analysis\n\nIf n is the number of nodes...\n\nThe algorithm only requires ***```O(1)```*** extra space on the heap, ***BUT*** in the worst case, it requires ***```O(n)```*** extra space on the stack, as we could need to put the entire list on. \n\nThe amount of space required is dependent on:\n1) The length of the longest stretch of nodes that only have child or next pointers.\n2) The percentage of nodes which have both a child and a next pointer on them (the higher the percentage, the better the performance, because we have nearer to a balanced tree structure).\n\nDue to this structure being equivalent to a (rather stringy in a lot of cases I suspect) binary tree, I\'m pretty sure  it\'s impossible to write an iterative algorithm that uses ***```O(1)```*** space. The stack/ queue you use to keep track of the work still to do could potentially grow to ***```O(n)```*** in the worst case, and like I said, this worst case is probably common.\n\nThe time complexity is ***```O(n)```*** . We handle each node once. It is impossible to do better than ***```O(n)```*** time, because we need to actually check the child and next pointers of every node, otherwise we could miss some parts of the structure out!\n\n## Algorithm\n\n```py\nclass Solution(object):\n    def flatten(self, head):\n        """\n        :type head: Node\n        :rtype: Node\n        """\n        self.recursively_flatten(head)\n        return head\n    \n    # Takes the head of the list to be flattened, and returns the tail of the flattened list.\n    def recursively_flatten(self, head):\n        \n        # Could happen if outer caller passes in an empty list.\n        if head == None:\n            return None\n        \n        # Base case - there is nothing left to flatten.\n        if head.next == None and head.child == None:\n            return head\n        \n        # Recursive case - we need to flatten the child and the tail.\n        tail = head.next # We need to store this as doing child first.\n        current_end = head # Where will we be attaching next?\n        \n        if head.child != None:\n            child_end = self.recursively_flatten(head.child)\n            self.link(current_end, head.child)\n            current_end = child_end\n            head.child = None\n            \n        if tail != None:\n            tail_end = self.recursively_flatten(tail)\n            self.link(current_end, tail)\n            current_end = tail_end\n            \n        return current_end\n    \n    def link(self, node_1, node_2):\n        node_1.next = node_2\n        node_2.prev = node_1\n```\n\n## Another way of looking at it...\nAnother interesting observation one could make is that this linked list structure is actually a binary tree!\n Instead of having left/ right nodes to "child" through, we have child/next. \n \n If we pretend that "child" means the left node, and "next" means the right node, then the order of nodes in the linked list the pre-order traversal of the "tree". \n \n We first included the node itself, and then the result of going over left (tail), and finallly the result of going over right (next). 
[]