Flatten a Multilevel Doubly Linked List LeetCode solution in Python

1
"""
2
# Definition for a Node.
3
class Node:
4
    def __init__(self, val, prev, next, child):
5
        self.val = val
6
        self.prev = prev
7
        self.next = next
8
        self.child = child
9
"""
10

11

12
class Solution:
13
    def flatten(self, head: "Optional[Node]") -> "Optional[Node]":
14
        node = head
15
        while node:
16
            if node.child:  # If there is a child travel to last node of the child
17
                child = node.child
18
                while child.next:
19
                    child = child.next
20
                child.next = (
21
                    node.next
22
                )  # Update the next of child to the the next of the current node
23
                if (
24
                    node.next
25
                ):  # update the prev of the next node to chile to make it valid doubly linked list
26
                    node.next.prev = child
27
                node.next = (
28
                    node.child
29
                )  # Update the child to become the next of the current
30
                node.next.prev = node  # update the prev of the next node to chile to make it valid doubly linked list
31
                node.child = None  # Make the child of the current node None to fulfill the requirements
32
            node = node.next
33
        return head
34

35

36
# time and space complexity
37
# time: O(n)
38
# space: O(1)