Python Program to Flatten a Linked List with Child Pointers

Overview

This Python program flattens a multilevel linked list. The linked list contains nodes that have two pointers: one to the next node in the list and another to a child node, which may have its own next and child pointers. The program flattens this multilevel linked list into a single-level list by merging all the child lists into the main list.

Program Explanation

The structure of the program includes a Node class to represent a node in the linked list, and a function to flatten the list with child pointers.

Steps Involved:

1. Create a class Node to represent the elements of the linked list. Each node has three attributes: data (the value of the node), next (pointer to the next node), and child (pointer to a child node).
2. Create a function flatten_list that takes the head of a linked list and flattens it by merging all child lists into the main list.
3. Use an iterative approach to traverse the list. If a node has a child, merge the child list into the main list by adjusting the next pointers. Move the current pointer forward until the end of the list is reached.
4. The child pointers are removed, and the list is converted into a single-level list.

Python Code


class Node:
"""
Node class to represent a linked list node with child pointers.
Each node contains the data, a pointer to the next node, and a pointer to a child node.
"""
def __init__(self, data):
self.data = data
self.next = None
self.child = None

def flatten_list(head):
“””
Flatten a multilevel linked list where nodes may have child pointers into a single-level list.

:param head: Head node of the linked list
:return: Head node of the flattened linked list
“””
if not head:
return None

current = head

while current is not None:
if current.child:
# Save the next node to reconnect after flattening the child list
next_node = current.next

# Flatten the child list
child_list_head = current.child
current.next = child_list_head # Merge child list into main list
current.child = None # Remove child pointer

# Find the tail of the flattened child list
temp = child_list_head
while temp.next is not None:
temp = temp.next

# Connect the tail of the child list to the next node
temp.next = next_node
current = current.next

return head

# Helper function to print a linked list
def print_linked_list(head):
“””
Print the elements of a linked list starting from the head node.

:param head: Head node of the linked list
“””
current = head
while current is not None:
print(current.data, end=” -> “)
current = current.next
print(“None”)

# Example usage:
# Create a multilevel linked list:
# 1 -> 2 -> 3 -> None
# |
# 7 -> 8 -> None
# |
# 10 -> 11 -> None
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

head.next.child = Node(7)
head.next.child.next = Node(8)

head.next.child.next.child = Node(10)
head.next.child.next.child.next = Node(11)

print(“Original Multilevel Linked List:”)
print_linked_list(head)

# Flatten the list
flatten_list(head)

print(“Flattened Linked List:”)
print_linked_list(head)

Program Explanation

This Python program defines the following:

• Node class: Each node in the linked list contains a value (data), a reference to the next node (next), and a reference to a child node (child).
• flatten_list function: This function flattens the linked list by traversing the nodes. Whenever a child list is found, it is merged into the main list by adjusting the next pointers. The child pointers are removed, and the list is converted into a single-level list.
• print_linked_list function: A utility function to display the linked list both before and after flattening for clarity.

Example Output

Given the multilevel linked list:

• 1 -> 2 -> 3 -> None
• |
• 7 -> 8 -> None
• |
• 10 -> 11 -> None

After flattening, the linked list will be:

1 -> 2 -> 7 -> 8 -> 10 -> 11 -> 3 -> None