https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list

In this problem we need to traverse our multilevel doubly linked list in some special order and rebuild some connections. We can consider our list as graph, which we now need to traverse. What graph traversal algorighms do we know? We should think about dfs and bfs. Why I choose dfs? Because we need to traverse as deep as possible, before we traverse neibhour nodes, and that is what dfs do exactly! When you realise this, problem becomes much more easier. So, algorighm look like:

  1. Put head of our list to stack and start to traverse it: pop element from it and add two two elements instead: its next and its child. The order is important: we first want to visit child and then next, that is why we put child to the top of our stack.
  2. Each time we pop last element from stack, I write it to auxilary order list.
  3. Last step is to rebuild from our order list flattened doubly linked list.

Complexity: time complexity is O(n), where n is number of nodes in our list. In this approach we also use O(n) additional space, because I keep order list. This can be avoid, if we make connections on the fly, but it is a bit less intuitive in my opinion, but ofcourse more optimal in space complexity.

class Solution:
    def flatten(self, head):
        if not head: return head
        stack, order = [head], []

        while stack:
            last = stack.pop()
            order.append(last)
            if last.next:
                stack.append(last.next)
            if last.child:
                stack.append(last.child)
        
        for i in range(len(order) - 1):
            order[i+1].prev = order[i]
            order[i].next = order[i+1]
            order[i].child = None
            
        return order[0]

Solution without extra array: the same idea, where we reconnect our nodes directly, without order array. It is O(h) in memory, where h is number of levels (in the worst case it will be O(n)).

class Solution(object):
    def flatten(self, head):
        if not head: return head
        
        dummy = Node(0)
        curr, stack = dummy, [head]
        while stack:
            last = stack.pop() 
            if last.next:
                stack.append(last.next)
            if last.child:
                stack.append(last.child)
            curr.next = last
            last.prev = curr  
            last.child = None
            curr = last
        
        res = dummy.next
        res.prev = None
        return res

If you like the solution, you can upvote it on leetcode discussion section: Problem 0430