Flatten a Linked List with Child Pointers in Go

Program Code

package main

import "fmt"

// Node defines a node in a multi-level linked list with child pointers
type Node struct {
    Val    int
    Next   *Node
    Child  *Node
}

// flatten flattens a multi-level linked list into a single-level linked list
func flatten(head *Node) *Node {
    if head == nil {
        return nil
    }

    dummy := &Node{}
    current := dummy
    stack := []*Node{head}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        current.Next = node
        current = current.Next

        if node.Next != nil {
            stack = append(stack, node.Next)
        }
        if node.Child != nil {
            stack = append(stack, node.Child)
            node.Child = nil
        }
    }

    return dummy.Next
}

// Helper function to print the linked list
func printList(head *Node) {
    for head != nil {
        fmt.Print(head.Val, " ")
        head = head.Next
    }
    fmt.Println()
}

// Main function to test the flatten function
func main() {
    // Create a multi-level linked list
    // List: 1 -> 2 -> 3 -> 4 -> 5 -> 6
    // Child of 3: 7 -> 8 -> 9
    // Child of 8: 10 -> 11
    // Child of 9: 12

    // Create child lists
    child3 := &Node{7, &Node{8, &Node{9, &Node{12, nil}}}}
    child8 := &Node{10, &Node{11, nil}}

    // Create main list with children
    head := &Node{1, &Node{2, &Node{3, &Node{4, &Node{5, &Node{6, nil}}}}}}
    head.Next.Next.Child = child3
    child3.Next.Child = child8

    fmt.Print("Original List: ")
    printList(head)

    // Flatten the multi-level linked list
    flattened := flatten(head)

    fmt.Print("Flattened List: ")
    printList(flattened)
}
    

Explanation

The Go program is designed to flatten a multi-level linked list into a single-level linked list. Here is a detailed explanation of the program structure:

1. Node Definition

The Node struct defines a node in a multi-level linked list. Each node contains:

• Val: The value of the node.
• Next: A pointer to the next node in the same level.
• Child: A pointer to a child node (which itself may have its own next and child nodes).

2. flatten Function

The flatten function flattens the multi-level linked list:

• Initializes a dummy node and a stack to help with the traversal.
• Uses a stack to perform a depth-first traversal of the linked list:
  • Pops the top node from the stack and appends it to the current node’s next pointer.
  • If the node has a next pointer, pushes it onto the stack.
  • If the node has a child pointer, pushes it onto the stack and sets the child pointer to nil.
• Returns the flattened list starting from the dummy node’s next pointer.

3. printList Function

The printList function is a utility to print out the values of the linked list for demonstration purposes.

4. Main Function

The main function demonstrates the usage of the flatten function:

• Creates a sample multi-level linked list with child pointers.
• Prints the original multi-level linked list.
• Flattens the list using flatten and prints the result.