Flatten a Linked List with Child Pointers Using Python

This Python program demonstrates how to flatten a linked list where each node may contain a next pointer and a child pointer, which points to a separate linked list. The goal is to modify the list such that all nodes appear in a single-level depth linked list, ordered as they appear in depth-first sequence.

Python Code

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.child = None

def flatten_list(head):
    if not head:
        return None

    # Pseudo-stack to manage nodes
    stack = []
    current = head

    while current or stack:
        if current.child:
            if current.next:
                stack.append(current.next)
            current.next = current.child
            current.child = None

        if not current.next and stack:
            current.next = stack.pop()

        current = current.next

    return head

# Example Usage
# Create a linked list with child pointers and flatten it
head = Node(1)
head.child = Node(2)
head.child.next = Node(3)
head.next = Node(4)
flattened = flatten_list(head)
current = flattened
while current:
    print(current.value)
    current = current.next

Explanation of the Code

The program uses a class Node to represent each node in the linked list. Each node has a value, a next pointer to the next node in the same list, and a child pointer to the head of another linked list.

The flatten_list function begins at the head of the list and traverses each node, connecting child nodes into the main list and using a stack to manage nodes that continue after a child list. This ensures all nodes are visited in a depth-first manner, and the original list structure is flattened into a single-level list.

Output and Use Case

The example constructs a linked list with both next and child pointers and then flattens it. The output will display nodes in the order: 1, 2, 3, 4, showing the depth-first flattening of the list.