Flatten a Multilevel Linked List in C

This program demonstrates how to flatten a multilevel linked list where each node may contain a child pointer that points to another linked list. The goal is to transform this list into a single-level linked list, making all child nodes into nodes of the main list, while maintaining their order.

Program Explanation

The program utilizes a linked list node structure that includes both a next pointer and a child pointer. Functions included in the program create nodes, append child and sibling nodes, flatten the list, and display the flattened list.

• struct Node: Defines the structure of the list node, which includes pointers to both the next and child nodes.
• createNode: Allocates a new node with given data.
• flattenList: Flattens the linked list by appending child nodes to the end of the main list.
• printList: Outputs the list to demonstrate the flattening process.

Source Code

#include <stdio.h>
#include <stdlib.h>

// Node structure for a multilevel linked list
struct Node {
    int data;
    struct Node* next;
    struct Node* child;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->child = NULL;
    return newNode;
}

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

    struct Node *tmp, *tail = head;
    while (tail->next)
        tail = tail->next;  // Find last node

    struct Node* cur = head;
    while (cur != tail) {
        if (cur->child) {
            tail->next = cur->child;  // Attach child at the end of the list
            tmp = cur->child;
            while (tmp->next) tmp = tmp->next;  // Advance to new last node
            tail = tmp;
        }
        cur = cur->next;  // Process next node
    }

    return head;
}

// Function to print the nodes in a linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\\n");
}

int main() {
    struct Node* head = createNode(1);
    head->child = createNode(2);
    head->child->child = createNode(3);

    head->next = createNode(4);
    head->next->child = createNode(5);
    head->next->child->next = createNode(6);

    printf("Original List: \\n");
    printList(head);  // Print before flattening for clarity, assuming a function that handles levels

    head = flattenList(head);

    printf("Flattened List: \\n");
    printList(head);

    return 0;
}
        

Conclusion

The provided C program flattens a multilevel linked list into a single-level linked list. By connecting the end of the main list to the child lists and then continuing until no more child nodes are left, the program successfully linearizes the structure without using additional space.