Python O(n), O(1) easy solution with explanation
Easy iterative approach without using extra memory.\nO(n) time complexity\nO(1) space complexity\n\n\n"""\n# Definition for a Node.\nclass Node(object):\n    de
Easy iterative approach without using extra memory.\nO(n) time complexity\nO(1) space complexity\n\n```\n"""\n# Definition for a Node.\nclass Node(object):\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(object):\n    def flatten(self, head):\n        """\n        :type head: Node\n        :rtype: Node\n        """\n        # traverse the list and look for nodes, where self.child is not None\n        # keep the pointer to the previous node and to the original next node\n        # merge a child list to the parent list - connect prev and next pointers\n        # continue traversing until encountering another node where self.child is not None, \n        # or reaching the end of the main list\n        \n        current = head\n        \n        while current is not None:\n            # check for child node\n            if current.child is not None:\n                # merge child list into the parent list\n                self.merge(current)\n                \n            # move to the next node\n            current = current.next\n        \n        return head\n            \n    \n    def merge(self, current):\n        child = current.child\n        \n        # traverse child list until we get the last node\n        while child.next is not None:\n            child = child.next\n        \n        # child is now pointing at the last node of the child list\n        # we need to connect child.next to current.next, if there is any\n        if current.next is not None:\n            child.next = current.next\n            current.next.prev = child\n        \n        # now, we have to connect current to the child list\n        # child is currently pointing at the last node of the child list, \n        # so we need to use pointer (current.child) to get to the first node of the child list\n        current.next = current.child\n        current.child.prev = current\n        \n        # at the end remove self.child pointer\n        current.child = None\n        \n```
['Iterator', 'Python', 'Python3']