87888990919293949596979899100101102103104105106107
class ListNode:
    def __init__(self, val=0, next=None, child=None):
        self.val = val
        self.next = next
        self.child = child

class Solution:
    # Function to convert a vector to a linked list
    def convertArrToLinkedList(self, arr):
        ''' Create a dummy node to serve as
         the head of the linked list '''
        dummyNode = ListNode(-1)
        temp = dummyNode

        ''' Iterate through the vector and
         create nodes with vector elements '''
        for i in range(len(arr)):
            # Create a new node with the vector element
            temp.child = ListNode(arr[i])
            
            # Update the temporary pointer
            temp = temp.child
        
        ''' Return the linked list starting
         from the next of the dummy node '''
        return dummyNode.child

    # Function to flatten a linked list with child pointers 
    def flattenLinkedList(self, head):
        arr = []

        # Traverse through the linked list
        while head is not None:
            ''' Traverse through the child
             nodes of each head node '''
            t2 = head
            
            while t2 is not None:
                # Store each node's data in the array
                arr.append(t2.val)
                
                # Move to the next child node
                t2 = t2.child

            # Move to the next head node
            head = head.next

        # Sort the array containing node values
        arr.sort()

        # Convert the sorted array back to a linked list
        return self.convertArrToLinkedList(arr)

# Function to print the linked list
def printLinkedList(head):
    while head is not None:
        print(head.val, end=" ")
        head = head.child
    print()

# Function to print the linked list in a grid-like structure
def printOriginalLinkedList(head, depth):
    while head is not None:
        print(head.val, end="")

        ''' If child exists, recursively
         print it with indentation '''
        if head.child:
            print(" -> ", end="")
            printOriginalLinkedList(head.child, depth + 1)

        # Add vertical bars for each level in the grid
        if head.next:
            print()
            for i in range(depth):
                print("| ", end="")
        
        head = head.next

if __name__ == "__main__":
    # Create a linked list with child pointers
    head = ListNode(5)
    head.child = ListNode(14)

    head.next = ListNode(10)
    head.next.child = ListNode(4)

    head.next.next = ListNode(12)
    head.next.next.child = ListNode(20)
    head.next.next.child.child = ListNode(13)

    head.next.next.next = ListNode(7)
    head.next.next.next.child = ListNode(17)

    # Print the original linked list structure
    print("Original linked list:")
    printOriginalLinkedList(head, 0)

    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to flatten the linked list
    flattened = sol.flattenLinkedList(head)
    
    # Printing the flattened linked list
    print("\nFlattened linked list: ", end="")
    printLinkedList(flattened)
12345678910111213141516171819202122232425262728293031<