Flatten Linked List with Child Pointers – Java Program

This Java program demonstrates how to flatten a multi-level linked list where each node has a child pointer that points to another linked list. The goal is to flatten this list into a single-level linked list.

Program Structure

The program is structured into three main components:

1. ListNode Class: Defines the node structure for the linked list, including child pointers.
2. FlattenLinkedList Class: Contains the method to flatten the multi-level linked list.
3. Main Class: Contains the main method to execute the program and test the flattening functionality.

Java Code

    /**
     * Definition for a singly-linked list with a child pointer.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode child;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next, ListNode child) { this.val = val; this.next = next; this.child = child; }
     * }
     */

    public class ListNode {
        int val;
        ListNode next;
        ListNode child;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next, ListNode child) { this.val = val; this.next = next; this.child = child; }
    }

    public class FlattenLinkedList {
        /**
         * Flattens a multi-level linked list into a single-level linked list.
         * 
         * @param head The head of the multi-level linked list.
         * @return The head of the flattened linked list.
         */
        public ListNode flatten(ListNode head) {
            if (head == null) return null;
            
            ListNode dummy = new ListNode(0);
            ListNode prev = dummy;
            flattenHelper(head, prev);
            dummy.next.next = null; // Disconnect the dummy node
            return dummy.next;
        }
        
        private ListNode flattenHelper(ListNode node, ListNode prev) {
            ListNode curr = node;
            ListNode tail = prev;
            
            while (curr != null) {
                tail.next = curr;
                tail = tail.next;
                
                // Store the next node to reconnect later
                ListNode next = curr.next;
                
                // If there's a child node, flatten it and reconnect
                if (curr.child != null) {
                    flattenHelper(curr.child, tail);
                    curr.child = null; // Clear the child pointer
                }
                
                curr = next;
            }
            
            return tail;
        }
    }

    public class Main {
        public static void main(String[] args) {
            // Create a multi-level linked list for testing
            ListNode childList = new ListNode(7, new ListNode(8, new ListNode(9, new ListNode(10))));
            ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, null, childList))))));
            
            // Flatten the multi-level linked list
            FlattenLinkedList flattener = new FlattenLinkedList();
            ListNode flattenedHead = flattener.flatten(head);
            
            // Print the flattened list
            System.out.println("Flattened linked list:");
            printList(flattenedHead);
        }
        
        // Helper method to print the linked list
        private static void printList(ListNode head) {
            ListNode current = head;
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.next;
            }
            System.out.println();
        }
    }
    

Explanation

ListNode Class: This class represents a node in the linked list, including a child pointer. Each node contains an integer value, a reference to the next node, and a reference to a child node (which can point to another linked list).

FlattenLinkedList Class: This class contains the method flatten that flattens a multi-level linked list into a single-level linked list. The method flattenHelper is used to recursively flatten each level and reconnect the nodes.

Main Class: This class is used for testing the flattening functionality. It creates a sample multi-level linked list, flattens it using the FlattenLinkedList class, and prints the result.