Flatten a Multilevel Linked List in C++

This C++ program demonstrates how to flatten a linked list where each node may contain a next pointer and a child pointer. The child pointer may point to another linked list which needs to be integrated into the main list at that point.

Program Code

#include <iostream>

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* child;

    Node() : val(0), next(nullptr), child(nullptr) {}
    Node(int _val) : val(_val), next(nullptr), child(nullptr) {}
    Node(int _val, Node* _next, Node* _child) : val(_val), next(_next), child(_child) {}
};

// Function to flatten the linked list
Node* flatten(Node* head) {
    if (!head) return head;

    Node* current = head;
    while (current != nullptr) {
        if (current->child) {
            Node* next = current->next;
            current->next = flatten(current->child);
            current->child = nullptr;

            // Find the tail of the newly added sublist
            Node* tail = current->next;
            while (tail->next != nullptr) {
                tail = tail->next;
            }
            tail->next = next;

            // If the original next node exists, set its child pointers correctly
            if (next) next->prev = tail;
        }
        current = current->next;
    }
    return head;
}

// Helper function to print the flattened linked list
void printFlattenedList(Node* node) {
    while (node != nullptr) {
        std::cout << node->val << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    // Creating nodes of the list
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->child = new Node(7);
    head->next->next->child->next = new Node(8);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    std::cout << "Original List: ";
    printFlattenedList(head);

    Node* flat = flatten(head);

    std::cout << "Flattened List: ";
    printFlattenedList(flat);

    return 0;
}

Explanation of the Code

The Node class defines the structure of the linked list nodes, which include integer values and pointers to the next node and a child node. The flatten function iterates through the list, and whenever it encounters a node with a child, it recursively flattens the child list and merges it at that position. It also ensures to reconnect any subsequent nodes in the main list correctly.

Conclusion

This program effectively flattens a multilevel linked list into a single-level list using recursion and careful pointer manipulation. The process maintains all original nodes in their new positions without duplicating any node.