Problem Statement

Given a special linked list containing n head nodes where every node in the linked list contain two pointers:

• next points to the next node in the list
• child pointer to a linked list where the current node is the head.

Each of these child linked list is in sorted order and connected by a child pointer.

Flatten this linked list such that all nodes appear in a single layer connected by the child pointer and return the head of the modified list.

Examples

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The given linked list can be transformed into a single level sorted list by initializing an array to temporarily store nodes during traversal. Traverse the list, first following the top-level next pointers, then accessing each node's child pointers, adding all nodes to the array.

Sort the array to arrange the values sequentially, then create and return a new linked list from the sorted array.

Approach:

1. Initialize an array to store node values and traverse the list, collecting values from both top-level and child nodes.
2. Sort the array to arrange the values in ascending order.
3. Create and return a new linked list from the sorted array.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition of special linked list:
struct ListNode {
    int val;
    ListNode *next;
    ListNode *child;
    ListNode() {
        val = 0;
        next = NULL;
        child = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
        child = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode* next2) {
        val = data1;
        next = next1;
        child = next1;
    }
};

class Solution {

public:
    // Function to flatten a linked list with child pointers 
    ListNode* flattenLinkedList(ListNode* head) {
        vector<int> elements; // A vector to store all the values from the list

        // Step 1: Traverse the parent and child nodes to collect all values
        ListNode* parent = head; // Start with the head of the list
        while (parent != nullptr) {
            elements.push_back(parent->val); // Add the value of the current node

            ListNode* child = parent->child; // Access the child list
            while (child != nullptr) {
                elements.push_back(child->val); // Add values from the child list
                child = child->child; // Move to the next child (should likely be child->next for horizontal traversal)
            }
            parent = parent->next; // Move to the next parent node
        }

        // Step 2: Sort the collected values
        sort(elements.begin(), elements.end()); // Sort the values in ascending order

        // Step 3: Convert the sorted values into a new flattened linked list
        ListNode* dummy = new ListNode(0); // Create a dummy node to simplify list creation
        ListNode* current = dummy; // Pointer to the current node being created
        for (int i = 0; i < elements.size(); i++) {
            current->child = new ListNode(elements[i]); // Create a new node with the sorted value
            current = current->child; // Move to the next node
        }

        // Step 4: Return the head of the new flattened list (ignoring the dummy node)
        return dummy->child; // Return the first meaningful node
    }
};

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->child;
    }
    cout << endl;
}

// Function to print the linked list in a grid-like structure
void printOriginalLinkedList(ListNode* head, int depth) {
    while (head != nullptr) {
        cout << head->val;

        /* If child exists, recursively
         print it with indentation */
        if (head->child) {
            cout << " -> ";
            printOriginalLinkedList(head->child, depth + 1);
        }

        // Add vertical bars for each level in the grid
        if (head->next) {
            cout << endl;
            for (int i = 0; i < depth; ++i) {
                cout << "| ";
            }
        }
        head = head->next;
    }
}

int main() {
    // Create a linked list with child pointers
    ListNode* head = new ListNode(5);
    head->child = new ListNode(14);

    head->next = new ListNode(10);
    head->next->child = new ListNode(4);

    head->next->next = new ListNode(12);
    head->next->next->child = new ListNode(20);
    head->next->next->child->child = new ListNode(13);

    head->next->next->next = new ListNode(7);
    head->next->next->next->child = new ListNode(17);

    // Print the original linked list structure
    cout << "Original linked list:" << endl;
    printOriginalLinkedList(head, 0);

    // Creating an instance of Solution class
    Solution sol;
    
    // Function call to flatten the linked list
    ListNode* flattened = sol.flattenLinkedList(head);
    
    // Printing the flattened linked list
    cout << "\nFlattened linked list: ";
    printLinkedList(flattened);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(NxM) + O(NxM log(NxM)) + O(NxM) where N is the number of nodes along the next pointers and M is the number of nodes along the child pointers.
  • O(NxM) because we traverse through all the nodes, iterating through N nodes along the next pointers and M nodes along the child pointers.
  • O(NxM log(NxM)) because we sort the array containing NxM total elements.
  • O(NxM) because we reconstruct the linked list from the sorted array by iterating over the NxM elements.
• Space Complexity: O(NxM) + O(NxM) where N is the number of nodes along the next pointers and M is the number of nodes along the child pointers.
  • O(NxM) for storing all the elements in an additional array for sorting.
  • O(NxM) to reconstruct the linked list from the array after sorting.

2️⃣ Optimal Approach

Intuition:

The optimized approach is based on the fact that the child linked lists are already sorted. By merging these pre-sorted lists directly during traversal, we can eliminate the additional space and time complexity generated by sorting.

Instead of collecting all node values into an array and then sorting them, we can merge these sorted vertical linked lists efficiently in place. This eliminates the need for additional sorting steps and avoids allocating extra space for the combined linked list.

The base case ensures the termination of the recursion when there's either no list or only a single node remaining. The recursive function then handles the merging of the remaining lists after recursive flattening, creating a sorted flattened linked list.

Approach:

1. Establish base case conditions by checking if the head is null or has no next pointer. If either condition is met, return the head, as there is no further flattening or merging required.
2. Recursively initiate the flattening process by calling flattenLinkedList on the next node (head -> next). The result of this recursive call will be the head of the flattened and merged linked list.
3. Within the recursive call, perform merge operations by calling a merge function. This function merges the current list with the already flattened and merged list based on their data values. The merged list is then updated in the head and returned as the result of the flattening process.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition of special linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode *child;
    ListNode() {
        val = 0;
        next = NULL;
        child = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
        child = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode* next2) {
        val = data1;
        next = next1;
        child = next1;
    }
};

class Solution {
private:
    /* Merge the two linked lists in a particular
     order based on the data value */
    ListNode* merge(ListNode* list1, ListNode* list2){
        /* Create a dummy node as a 
        placeholder for the result */
        ListNode* dummyNode = new ListNode(-1);
        ListNode* res = dummyNode;
    
        // Merge the lists based on data values
        while(list1 != NULL && list2 != NULL){
            if(list1->val < list2->val){
                res->child = list1;
                res = list1;
                list1 = list1->child;
            }
            else{
                res->child = list2;
                res = list2;
                list2 = list2->child;
            }
            res->next = NULL;
        }
    
        // Connect the remaining elements if any
        if(list1){
            res->child = list1;
        } else {
            res->child = list2;
        }
    
        // Break the last node's link to prevent cycles
        if(dummyNode->child){
            dummyNode->child->next = NULL;
        }
        
        return dummyNode->child;
    }

public:
    // Function to flatten a linked list with child pointers 
    ListNode* flattenLinkedList(ListNode* head) {
        // If head is null or there is no next node
        if(head == NULL || head->next == NULL){
            return head; // Return head
        }
    
        // Recursively flatten the rest of the linked list
        ListNode* mergedHead = flattenLinkedList(head->next);
        
        // Merge the lists
        head = merge(head, mergedHead);
        return head;
    }
};

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->child;
    }
    cout << endl;
}

// Function to print the linked list in a grid-like structure
void printOriginalLinkedList(ListNode* head, int depth) {
    while (head != nullptr) {
        cout << head->val;

        /* If child exists, recursively
         print it with indentation */
        if (head->child) {
            cout << " -> ";
            printOriginalLinkedList(head->child, depth + 1);
        }

        // Add vertical bars for each level in the grid
        if (head->next) {
            cout << endl;
            for (int i = 0; i < depth; ++i) {
                cout << "| ";
            }
        }
        head = head->next;
    }
}

int main() {
    // Create a linked list with child pointers
    ListNode* head = new ListNode(5);
    head->child = new ListNode(14);

    head->next = new ListNode(10);
    head->next->child = new ListNode(4);

    head->next->next = new ListNode(12);
    head->next->next->child = new ListNode(20);
    head->next->next->child->child = new ListNode(13);

    head->next->next->next = new ListNode(7);
    head->next->next->next->child = new ListNode(17);

    // Print the original linked list structure
    cout << "Original linked list:" << endl;
    printOriginalLinkedList(head, 0);

    // Creating an instance of Solution class
    Solution sol;
    
    // Function call to flatten the linked list
    ListNode* flattened = sol.flattenLinkedList(head);
    
    // Printing the flattened linked list
    cout << "\nFlattened linked list: ";
    printLinkedList(flattened);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(Nx(2M)) ~ O(2NxM) where N is the length of the linked list along the next pointer and M is the length of the linked list along the child pointers.
  • The merge operation in each recursive call takes time complexity proportional to the length of the linked lists being merged as they have to iterate over the entire lists. Since the vertical depth of the linked lists is assumed to be M, the time complexity for a single merge operation is proportional to O(2M).
  • This operation is performed N number of times (to each and every node along the next pointer list) hence the resultant time complexity becomes O(Nx2M).
• Space Complexity: O(1) as this code uses no external space or additional data structures to store values. But a recursive stack uses O(N) space to build the recursive calls for each node along the next pointer list.