Flatten a Multilevel Doubly Linked List — LeetCode 430 Python Solution

The problem

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes.

Example

Input

head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Output

[1,2,3,7,8,11,12,9,10,4,5,6]

Explanation

The multilevel linked list in the input is shown.

Python solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""


class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        def preorder(pre, cur):
            if cur is None:
                return pre
            cur.prev = pre
            pre.next = cur

            t = cur.next
            tail = preorder(cur, cur.child)
            cur.child = None
            return preorder(tail, t)

        if head is None:
            return None
        dummy = Node(0, None, head, None)
        preorder(dummy, head)
        dummy.next.prev = None
        return dummy.next

Complexity

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 430. Flatten a Multilevel Doubly Linked List is filed here because LeetCode tags it Linked List and Doubly-Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems