Flattening A Linked List In C++

In this guide, you will discover the process of flattening a linked list in C++ using various methods and illustrations.

Flattening a linked list in C++ refers to transforming a linked list of linked lists into one consolidated and sorted linked list. This task is frequently encountered in the realm of data structures and algorithms. A linked list of linked lists is a configuration where each node of the outer linked list points to an independent linked list, and the objective is to amalgamate these distinct linked lists into a solitary sorted linked list. Various techniques exist for flattening a linked list in C++. The primary methods for achieving this include:

Approach-1: Merge sort and Recursion

This method iteratively compresses the linked list and employs the merge procedure to combine separate linked lists in a sorted fashion. The resultant linked list will emerge as a unified sorted linked list encompassing all elements from the initial linked list of linked lists.

Program:

Let's consider a scenario to demonstrate the merge sort algorithm and the concept of recursion in the C++ programming language.

#include <iostream>
struct Node {
 int data;
 Node* next;
 Node* down;
};
Node* merge(Node* a, Node* b) {
 if (!a) return b;
 if (!b) return a;
 Node* result;
 if (a->data < b->data) {
 result = a;
 result->down = merge(a->down, b);
 } else {
 result = b;
 result->down = merge(a, b->down);
 }
 return result;
}
Node* flatten(Node* head) {
 if (!head || !head->next) {
 return head;
 }
 head->next = flatten(head->next);
 return merge(head, head->next);
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node;
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 10);
 insert(head, 19);
 insert(head, 28);
 insert(head->down, 7);
 insert(head->down, 8);
 insert(head->down, 30);
 insert(head->down->down, 20);
 insert(head->down->down, 22);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flatten(head);
 display(head);
 return 0;
}

Output:

5 7 10 19 20 28 35 40 45

Explanation:

• ✅ In this example, each node has three components: data , which stores the value of the node, next , a pointer to the next node in the same linked list, and down , a pointer to the next linked list.
• ✅ The merge function takes two sorted linked lists (a and b) as input and merges them into a single sorted linked list.
• ✅ It uses recursive calls to compare the data of nodes from the two lists and merge them accordingly.
• ✅ The result of merging is a new linked list that maintains the sorted order.
• ✅ The flatten function is responsible for flattening the linked list of linked lists.
• ✅ It takes the head of the linked list as input and recursively flattens the rest of the list.
• ✅ It first checks if the current list is empty or has only one element (!head || !head->next ), in which case it returns the list as it is.
• ✅ If there are more linked lists to be flattened ( head->next ), it recursively flattens the remaining part and then merges the current list with the flattened list using the merge function.
• ✅ The insert function is a utility function used to insert a new node with a specified data value at the end of a linked list.
• ✅ It checks if the linked list is empty (!head) , in which case it sets the new node as the head.
• ✅ Otherwise, it traverses the linked list to find the last node and appends the new node to the end.
• ✅ The display function is used to print the flattened linked list.
• ✅ It traverses the flattened list from the head to the end while printing each node's data value.
• ✅ In the main function, we create a sample linked list of linked lists using the insert function. We insert various elements into the linked lists in a hierarchical manner.
• ✅ After that, we call the flatten function to flatten the list.
• ✅ Finally, we display the flattened list using the display function.

Complexity Analysis:

Time Complexity:

• ✅ The merge function has a time complexity of O(n + m) , where n and m are the sizes of the two linked lists being merged.
• ✅ The flatten function recursively merges linked lists. Suppose there are 'k' linked lists and each linked list contains an average of 'n' elements. The time complexity is O(k n log(k)) because the merging process is performed recursively on each level of the hierarchy.
• ✅ The insert function inserts elements one by one, and for each insertion, it traverses the linked list to find the end. Therefore, the time complexity of insertion is O(n) , where 'n' is the size of the linked list at the time of insertion.
• ✅ The display function iterates through the flattened linked list once, so it has a time complexity of O(k * n) , where 'k' is the number of linked lists and 'n' is the total number of elements in the flattened list.
• ✅ Overall, the time complexity of the entire code can be approximated as O(k n log(k)) .

Space Complexity:

• ✅ The merge function has a space complexity of O(n + m) , where 'n' and 'm' are the sizes of the two linked lists being merged. This space is used for the recursive function call stack.
• ✅ In the worst case, the space complexity is O(k), where 'k' is the number of linked lists.
• ✅ The insert function allocates space for a new node for each insertion. In the worst case, the space complexity is O(n) , where 'n' is the number of elements inserted.
• ✅ The display function uses a constant amount of extra space, so its space complexity is O(1) .
• ✅ Overall, the space complexity of the code depends on the number of linked lists ('k') and the total number of elements ('n') in the flattened list. In the worst case, the space complexity can be approximated as O(k + n) .

Approach-2: Using Priority queue.

A priority queue is a data structure that allows elements with a certain priority to be inserted and extracted efficiently. In this case, the priority will be determined by the data value of the nodes.

• ✅ Create a min-heap (priority queue) to efficiently manage the next nodes from the linked lists.
• ✅ Initialize an empty result list that will store the flattened linked list.
• ✅ Initially, insert the head of each linked list into the priority queue.

While the priority queue is not empty:

• ✅ Extract the node with the smallest data value from the priority queue.
• ✅ Add this node to the result list.
• ✅ If this node has a "down" pointer (i.e., it's part of a linked list), insert the next node from the same linked list into the priority queue.

Continue this procedure until the priority queue has been depleted.

Program:

Let's consider an illustration to showcase how to flatten a linked list by utilizing a priority queue in C++.

#include <iostream>
#include <queue>
struct Node {
 int data;
 Node* next;
 Node* down;
};
// Comparison function for the priority queue
struct NodeComparison {
 bool operator()(const Node* a, const Node* b) const {
 return a->data > b->data;
 }
};
Node* flattenUsingPriorityQueue(Node* head) {
 // Create a priority queue (min-heap) to manage nodes
 std::priority_queue<Node*, std::vector<Node*>, NodeComparison> minHeap;
 // Push the top nodes of each list into the priority queue
 for (Node* current = head; current != nullptr; current = current->next) {
 minHeap.push(current);
 }
 Node* dummy = new Node(); // Create a dummy node to simplify list construction
 Node* tail = dummy; // Tail pointer for the result list
 // Merge the lists from the priority queue
 while (!minHeap.empty()) {
 Node* current = minHeap.top();
 minHeap.pop();
 // Add the node to the result list
 tail->next = current;
 tail = current;
 // If the node has a "down" pointer, push it into the priority queue
 if (current->down) {
 minHeap.push(current->down);
 }
 }
 return dummy->next; // Return the flattened list (excluding the dummy node)
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the flattened linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->next;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 10);
 insert(head, 19);
 insert(head, 28);
 insert(head->down, 7);
 insert(head->down, 8);
 insert(head->down, 30);
 insert(head->down->down, 20);
 insert(head->down->down, 22);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenUsingPriorityQueue(head);
 display(head);
 return 0;
}

Output:

5 7 10 19 20 28 35 40 45

Explanation:

• ✅ The code defines a Node structure to represent nodes in the linked list. Each node has an integer data, a pointer to the next node in the same linked list (next), and a pointer to the next linked list (down).
• ✅ A custom comparison function named NodeComparison is defined to compare nodes based on their data values in a way that ensures that the node with the smallest data value is at the top of the priority queue (min-heap).
• ✅ This function is responsible for flattening the linked list of linked lists using a priority queue.
• ✅ It takes the head of the linked list of linked lists as input.
• ✅ A min-heap (priority queue) minHeap is created to efficiently manage nodes based on their data values.
• ✅ The function iterates through the outer linked list to push the top nodes of each inner linked list into the priority queue.
• ✅ A dummy node (dummy) is created to simplify list construction, and a tail pointer is used to keep track of the last node in the result list.
• ✅ In the while loop , nodes are popped from the priority queue in order of their data values, and they are appended to the result list. If a node has a "down" pointer, the next node from the same linked list is pushed into the priority queue.
• ✅ The result list is returned, excluding the dummy node.
• ✅ The insert function is a utility function used to insert a new node at the end of a linked list.
• ✅ It checks if the linked list is empty or not and appends the new node accordingly.
• ✅ The display function is a utility function to print the flattened linked list.
• ✅ In the main function, a sample linked list of linked lists is created using the insert function. Various elements are inserted into the linked lists in a hierarchical manner.
• ✅ The flattenUsingPriorityQueue function is called to flatten the list.
• ✅ Finally, the flattened list is displayed using the display function.

Complexity Analysis:

Time Complexity:

• ✅ The for loop that iterates through the outer linked list and pushes the top nodes of each inner linked list into the priority queue has a time complexity of O(k * log(k)) , where 'k' is the number of linked lists. The insertion operation into a priority queue takes O(log(k)) time.
• ✅ The while loop runs until the priority queue is empty. In each iteration, it pops a node from the priority queue and pushes the next node from the same linked list into the queue (if applicable). The number of iterations is determined by the total number of nodes in the linked lists, which is 'n.' Therefore, the time complexity of the while loop is O(n * log(k)) in the worst case.
• ✅ Overall, the time complexity of the code is O(k log(k) + n log(k)) .

Space Complexity:

• ✅ The priority queue ( minHeap ) is used to store at most 'k' nodes at any given time. The space complexity for the priority queue is O(k) .
• ✅ A new flattened linked list is constructed during the merging process. The space required to store this list is O(n) , where 'n' is the total number of nodes in the flattened list.
• ✅ The code uses a few additional variables and pointers, but their space complexity is constant (O(1)) .
• ✅ Overall, the space complexity of the code is O(k + n) , where 'k' is the number of linked lists, and 'n' is the total number of nodes in the flattened list.

Approach-3: Using stack

This method is generally more efficient in terms of memory compared to employing a priority queue and is applicable to both arranged and disarranged linked lists. In this strategy, we make use of a stack to maintain a record of the nodes within the current level (linked list).

We initiate by pushing the highest nodes of every linked list onto the stack. While handling the top node, we add the subsequent node from the corresponding linked list to the stack if there is one. This procedure persists until the stack becomes empty.

Program:

Let's consider an example to illustrate the process of flattening a linked list using a stack in C++.

#include <iostream>
#include <stack>
struct Node {
 int data;
 Node* next;
 Node* down;
};
Node* mergeSortedLists(Node* a, Node* b) {
 if (!a) return b;
 if (!b) return a;
 Node* result = nullptr;
 if (a->data < b->data) {
 result = a;
 result->down = mergeSortedLists(a->down, b);
 } else {
 result = b;
 result->down = mergeSortedLists(a, b->down);
 }
 return result;
}
Node* flattenUsingStack(Node* head) {
 if (!head) return nullptr;
 std::stack<Node*> nodeStack;
 // Push the head node of each list onto the stack
 for (Node* current = head; current != nullptr; current = current->next) {
 nodeStack.push(current);
 }
 while (nodeStack.size() > 1) {
 Node* list1 = nodeStack.top();
 nodeStack.pop();
 Node* list2 = nodeStack.top();
 nodeStack.pop();
 // Merge the two sorted lists and push the result back onto the stack
 Node* mergedList = mergeSortedLists(list1, list2);
 nodeStack.push(mergedList);
 }
 return nodeStack.top();
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the flattened linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 7);
 insert(head, 10);
 insert(head, 19);
 insert(head->down, 20);
 insert(head->down, 22);
 insert(head->down->down, 28);
 insert(head->next, 30);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenUsingStack(head);
 display(head);
 return 0;
}

Output:

5 7 10 19 20 28 30 35 40 45

Explanation:

• ✅ In this program, the Node structure is used to represent the nodes of the linked list. Each node contains an integer data, a pointer to the next node in the same linked list (next) , and a pointer to the next linked list (down) .
• ✅ This function is used to merge two sorted linked lists and return the merged result.
• ✅ It takes two pointers a and b, which represent the heads of the two sorted lists to be merged.
• ✅ The function compares the data values of the nodes in a and b. It recursively selects the smaller value and appends it to the result. The down pointers are updated to merge the sublists.
• ✅ It is the main function for flattening the linked list.
• ✅ It uses a stack to manage nodes while flattening and sorting the linked list.
• ✅ Initially, it pushes the head node of each list onto the stack.
• ✅ After that, it iteratively pops two nodes from the stack, merges them using the mergeSortedLists function, and pushes the result back onto the stack.
• ✅ This process continues until there is only one list left in the stack.
• ✅ This utility function is used to insert a new node at the end of a list. It appends a new node with the specified data value to the end of an existing list.
• ✅ This utility function is used to display the flattened linked list by iterating through it and printing the data values of each node.
• ✅ In the main function , a sample linked list of linked lists is constructed using the insert function. Various elements are added to the linked lists to create a hierarchical structure.
• ✅ The flattenUsingStack function is called to flatten and sort the list. The result is stored in the head variable.
• ✅ Finally, the display function is used to print the flattened and sorted linked list.
• ✅ The output of the code will be the flattened and sorted linked list in ascending order. The code uses a stack to efficiently manage the nodes and ensures that the flattened list is sorted correctly.

Complexity Analysis:

Time Complexity:

• ✅ The flattenUsingStack function pushes and pops nodes in the stack, and for each pair of nodes, it calls mergeSortedLists . In the worst case, the stack size may be proportional to the total number of nodes in the linked lists, which we'll denote as 'N' . As a result, the time complexity is O(N * (m + n)) , where 'N' is the total number of nodes, and 'm' and 'n' are the sizes of the lists being merged.
• ✅ These functions iterate through the linked lists once. Their time complexity is O(N) , where 'N' is the total number of nodes.
• ✅ Overall, the time complexity of the entire code is O(N * (m + n)) .

Space Complexity:

• ✅ The space used by the stack is proportional to the depth of the linked list of linked lists, which is equivalent to the number of linked lists ('k') . The maximum space required for the stack is O(k) .
• ✅ A new flattened and sorted linked list is constructed during the merging process. The space required to store this list is O(N) , where 'N' is the total number of nodes in the flattened list.
• ✅ The code uses a few additional variables and pointers, but their space complexity is constant (O(1)) .
• ✅ Overall, the space complexity of the code is O(k + N) .

Approach-4: Using In-place Rearrangement method

The technique known as the "In-Place Rearrangement Method" is a strategy for flattening a linked list composed of nested linked lists. The objective is to reorganize the pointers within the current nodes in order to form a flattened linked list, all without the need for extra data structures. This method involves altering the structure of the original linked list.

Program:

Let's consider an illustration to showcase the process of flattening a linked list by employing the in-place rearrangement technique in C++.

#include <iostream>
struct Node {
 int data;
 Node* next;
 Node* down;
};
// Merge two sorted linked lists into a single sorted list
Node* mergeSortedLists(Node* a, Node* b) {
 if (!a) return b;
 if (!b) return a;
 Node* result = nullptr;
 if (a->data < b->data) {
 result = a;
 result->down = mergeSortedLists(a->down, b);
 } else {
 result = b;
 result->down = mergeSortedLists(a, b->down);
 }
 return result;
}
// Flatten and sort the linked list in ascending order
Node* flattenAndSort(Node* head) {
 if (!head || !head->next) return head;
 Node* mergedList = mergeSortedLists(head, flattenAndSort(head->next));
 return mergedList;
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 7);
 insert(head, 10);
 insert(head, 19);
 insert(head->down, 20);
 insert(head->down, 28);
 insert(head->next, 30);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenAndSort(head);
 display(head);
 return 0;
}

Output:

5 7 10 19 20 28 30 35 40 45

Explanation:

• ✅ In this example, the Node structure is used to represent the nodes of the linked list. Each node contains an integer data, a pointer to the next node in the same linked list (next), and a pointer to the next linked list (down).
• ✅ This function is used to merge two sorted linked lists into a single sorted list. It's implemented as a recursive
• ✅ It takes two pointers, a and b, which represent the heads of the two sorted lists to be merged.
• ✅ The down pointers are also updated to merge the sublists.
• ✅ It is the main function for flattening and sorting the linked list. It's implemented as a recursive function.
• ✅ It recursively flattens and sorts the list by merging pairs of lists.
• ✅ The base case is when there's only one list, or when the list has only one node (i.e., head or head->next is null).
• ✅ In the recursive case, it recursively flattens and merges the current list with the result of the flattened next list.
• ✅ This utility function is used to insert a new node at the end of a list. It appends a new node with the specified data value to the end of an existing list.
• ✅ This utility function is used to display the flattened linked list by iterating through it and printing the data values of each node.
• ✅ Finally, the display function is used to print the flattened and sorted linked list.
• ✅ The output of the code will be the flattened and sorted linked list in ascending order. The code efficiently flattens the linked lists using a merge sort-like approach.

Complexity Analysis:

Time complexity:

• ✅ The time complexity of merging two sorted linked lists with m and n elements is O(m + n) . In the worst case, it's called for all pairs, so its time complexity is O(N * (m + n)) , where 'N' is the total number of nodes, and 'm' and 'n' are the sizes of the lists being merged.
• ✅ The flattenAndSort function recursively flattens and sorts the linked list. In the worst case, it's called for each level of the linked list hierarchy, which results in a time complexity of O(k N (m + n)) , where 'k' is the number of levels.
• ✅ These functions iterate through the linked lists once. Their time complexity is O(N) , where 'N' is the total number of nodes.
• ✅ Overall, the time complexity of the entire code is O(k N (m + n)) .

Space Complexity:

• ✅ The code uses recursion for both mergeSortedLists and flattenAndSort . The space used for the recursion stack is proportional to the depth of the linked list of linked lists, which is equivalent to the number of linked lists ('k'). The maximum space required for the recursion stack is O(k) .
• ✅ The space required to store the sorted, flattened list is O(N) , where 'N' is the total number of nodes in the flattened list.
• ✅ The code uses a few additional variables and pointers, but their space complexity is constant (O(1)) .
• ✅ Overall, the space complexity of the code is O(k + N) .

Approach-5: Using a Dummy Node and Recursion

The technique of "Utilizing a Dummy Node and Recursion" offers a strategy for flattening a linked list containing nested linked lists. This method ensures that the sorted sequence is preserved without altering the initial structure. A dummy node is employed to recursively merge the sorted linked lists.

Program:

Let's consider an illustration to showcase how to flatten a linked list by employing a Dummy Node and Recursion in C++.

#include <iostream>
struct Node {
 int data;
 Node* next;
 Node* down;
};
Node* mergeSortedLists(Node* a, Node* b) {
 Node dummy;
 Node* tail = &dummy;
 dummy.down = nullptr;
 while (a && b) {
 if (a->data < b->data) {
 tail->down = a;
 a = a->down;
 } else {
 tail->down = b;
 b = b->down;
 }
 tail = tail->down;
 }
 tail->down = (a) ? a : b;
 return dummy.down;
}
Node* flattenUsingDummyAndRecursion(Node* head) {
 if (!head || !head->next) return head;
 Node* mid = head->next;
 Node* down = head->down;
 head->next = nullptr;
 Node* left = flattenUsingDummyAndRecursion(head);
 Node* right = flattenUsingDummyAndRecursion(mid);
 return mergeSortedLists(left, right);
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 7);
 insert(head, 10);
 insert(head, 19);
 insert(head->down, 20);
 insert(head->down, 28);
 insert(head->next, 30);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenUsingDummyAndRecursion(head);
 display(head);
 return 0;
}

Output:

5 7 10 19 20 30 35 40 45

Explanation:

• ✅ In this program, the Node structure represents the nodes of the linked list, with data for the value, nexcpp tutorialing to the next node at the same level, and down pointing to the next linked list (sublist).
• ✅ It merges two sorted linked lists using a dummy node . It iterates through the lists, selecting the smaller value to create a merged list. The down pointers are updated for sublists.
• ✅ The main function for flattening and sorting recursively divides the input list into two parts, processes each part, and merges them using mergeSortedLists . It maintains sorted order.
• ✅ The insert function appends a new node to the end of a list and display prints the flattened linked list.
• ✅ It constructs a sample hierarchical linked list comprising various elements and sublists.
• ✅ The code calls flattenUsingDummyAndRecursion on the head of the hierarchical list. Sublists are flattened, and the merged result is sorted in ascending order.
• ✅ The sorted, flattened linked list is displayed as the final output.
• ✅ This method efficiently preserves the original structure while creating a sorted flattened list, making it suitable for applications requiring both properties.

Complexity Analysis:

Time Complexity:

The time efficiency of this code is mainly influenced by two essential functions: mergeSortedLists and flattenUsingDummyAndRecursion.

The mergeSortedLists function operates with a time complexity of O(m + n) when merging two sorted linked lists of lengths 'm' and 'n'. This function is recursively invoked in the process of flattening for each pair of lists.

As part of the flattenUsingDummyAndRecursion function, the overall time complexity for mergeSortedLists is O(N * (m + n)), where 'N' signifies the total node count in the linked list, while 'm' and 'n' denote the sizes of the lists being merged.

The flattenUsingDummyAndRecursion Function is responsible for recursively flattening and arranging the linked list. It is invoked at every tier within the hierarchical arrangement, encompassing the complete list. The function's worst-case time complexity is O(k N (m + n)), with 'k' denoting the levels in the hierarchical structure.

Space Complexity:

• ✅ The code uses recursion for both mergeSortedLists and flattenUsingDummyAndRecursion. The space used for the recursion stack is proportional to the depth of the linked list hierarchy, which is equivalent to the number of linked lists ('k'). The maximum space required for the recursion stack is O(k) .
• ✅ The space required to store the sorted, flattened list is O(N) , where 'N' is the total number of nodes in the flattened list.
• ✅ The code uses a few additional variables and pointers, but their space complexity is constant (O(1)) .
• ✅ Overall, the space complexity of the code is O(k + N) , where 'k' represents the depth of the hierarchy, and 'N' is the total number of nodes in the flattened list. The code efficiently flattens and sorts the linked list while preserving the original structure.

Approach-6: Using Auxiliary array

The technique of "Utilizing an Auxiliary Array" is a strategy for flattening a linked list of linked lists while preserving their sorted sequence. In contrast to alternative techniques, this method avoids altering the original structure. Instead, it gathers the values from the linked list, arranges them with the help of an auxiliary array, and subsequently generates a fresh linked list based on the sorted values.

Program:

Here is the C++ code snippet that employs an additional array to flatten a linked list containing nested linked lists while preserving a sorted arrangement.

#include <iostream>
#include <vector>
#include <algorithm>
struct Node {
 int data;
 Node* next;
 Node* down;
};
// Function to flatten and sort the linked list using an auxiliary array
Node* flattenUsingAuxiliaryArray(Node* head) {
 if (!head) return nullptr;
 std::vector<int> values;
 // Traverse the linked list and collect values
 while (head) {
 Node* current = head;
 while (current) {
 values.push_back(current->data);
 current = current->down;
 }
 head = head->next;
 }
 //sort the collected values
 std::sort(values.begin(), values.end());
 // Create a new linked list from the sorted values
 Node* newHead = nullptr;
 Node* tail = nullptr;
 for (int value : values) {
 Node* newNode = new Node();
 newNode->data = value;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!newHead) {
 newHead = newNode;
 tail = newNode;
 } else {
 tail->down = newNode;
 tail = newNode;
 }
 }
 return newHead;
}
// Utility function to insert a new node at the end of a list
void insert(Node* &head, int data) {
 Node* newNode = new Node();
 newNode->data = data;
 newNode->next = nullptr;
 newNode->down = nullptr;
 if (!head) {
 head = newNode;
 } else {
 Node* temp = head;
 while (temp->next) {
 temp = temp->next;
 }
 temp->next = newNode;
 }
}
// Utility function to display the linked list
void display(Node* head) {
 while (head) {
 std::cout << head->data << " ";
 head = head->down;
 }
 std::cout << std::endl;
}
int main() {
 Node* head = nullptr;
 insert(head, 5);
 insert(head, 7);
 insert(head, 10);
 insert(head, 19);
 insert(head->down, 20);
 insert(head->down, 28);
 insert(head->next, 30);
 insert(head->next, 35);
 insert(head->next, 40);
 insert(head->next, 45);
 head = flattenUsingAuxiliaryArray(head);
 display(head);
 return 0;
}

Output:

5 7 10 19 20 30 35 40 45

Explanation:

• ✅ In this program, the Node structure represents the nodes of the linked list, with data for the value, nexcpp tutorialing to the next node at the same level, and down pointing to the next linked list (sublist).
• ✅ It is the central function responsible for flattening and sorting the linked list.
• ✅ It first traverses the input hierarchical linked list, collecting all the values and storing them in a dynamic array called values .
• ✅ The collected values array is sorted using a standard sorting algorithm ( std::sort ), ensuring that the values are in ascending order.
• ✅ A new linked list ( newHead ) is initialized to hold the flattened and sorted values.
• ✅ The code iterates through the sorted values and creates new nodes for each value, which are added to the end of the newHead
• ✅ The tail pointer tracks the last node of the list, allowing for efficient node insertion.
• ✅ The code includes two utility functions: insert , which inserts a new node at the end of a list, and display , which prints the flattened linked list.
• ✅ In the main function, a sample hierarchical linked list is constructed by inserting various elements and sublists.
• ✅ The flattenUsingAuxiliaryArray function is called on the head of the hierarchical list. The function processes and sorts the values into a new linked list.
• ✅ The code prints the sorted, flattened linked list as the final output.
• ✅ This method preserves the original structure of the linked lists while creating a sorted flattened list. However, it has a space complexity associated with the auxiliary array, which can be a drawback for large linked lists.

Complexity Analysis:

Time Complexity:

Gathering Data: The script iterates through the complete hierarchical linked list to gather values. This process entails examining each individual node, leading to a time complexity of O(N), where 'N' represents the overall node count in the hierarchical linked list.

Arranging the Data: The sorting process organizes the gathered values by utilizing std::sort. The time complexity for this task usually amounts to O(N * log(N)), with 'N' denoting the quantity of values requiring sorting.

Generating the Flattened List: Following the sorting process, the script loops through the arranged values to establish a fresh linked list. This construction phase also requires O(N) time as it examines each value only once.

In general, the efficiency of the code is primarily influenced by the sorting process, resulting in a time complexity of O(N * log(N)) at its worst.

Space Complexity:

An auxiliary array (referred to as values) is employed by the code to gather the values from the linked list. The space complexity associated with this array is O(N) as it accommodates 'N' values.

The flattened list is generated by initializing a fresh linked list that holds the sorted and flattened values. The storage space allocated for this list is O(N) due to the inclusion of 'N' nodes.

Additional Memory: The code introduces several extra variables and pointers, yet their spatial complexity remains constant at O(1).

The total space complexity of the code is O(N) , where 'N' denotes the total count of nodes within the hierarchical linked list.

Conclusion:

1. Merge Sort and Recursion:

This method employs a strategy similar to merge sort, incorporating recursion to both flatten and arrange the linked list. It proves to be effective, particularly for linked lists that are already sorted.

Pros: Maintains the original format, suitable for organized lists, and demonstrates a decent level of efficiency.

Cons: May not be the most space-efficient method.

Time and Space Complexity: The time complexity is O(N * log(N)) in the worst-case scenarios, while the space complexity varies based on the approach taken but can reach O(N).

2. Using Priority Queue:

The approach described involves utilizing a priority queue to combine and organize linked lists while executing the flattening procedure.

Advantages: Effective for disorganized lists, minimal space requirements.

Cons: Alters the initial format and could be less effective for organized lists.

Time and Space Complexity: The time complexity is O(N * log(K)), where 'K' represents the quantity of linked lists. As for space complexity, it is O(K) because of the priority queue implementation.

3. Using a Stack:

The method description outlines a technique that merges a stack with recursion to flatten and organize the linked list. This innovative strategy offers a versatile solution that can be customized for different situations.

Advantages: Maintains the initial format, flexible to suit various needs.

Cons: Recursion might consume extra stack space and could introduce complexity.

Time and Space Complexity: The time complexity is determined by the particular implementation, while the space complexity is influenced by the recursion depth and stack utilization.

4. In-Place Rearrangement:

This method involves reorganizing the pointers inside the nodes to generate a flattened linked list without the need for extra data structures.

Advantages: Maintains the initial layout, effectively utilizes available space.

Cons: Might involve greater intricacy in implementation and comprehension.

Time and Space Analysis: The time complexity is O(N) as it involves only one iteration. Regarding space complexity, it is O(1) since it alters the current arrangement without requiring additional memory allocation.

5. Using a Dummy Node and Recursion:

This approach involves utilizing a placeholder node along with recursive merging to flatten and arrange the elements in the linked list.

Advantages: Maintains initial format, simple to integrate.

Cons: Recursion can use additional stack space.

Time and Space Analysis: The time complexity in the worst-case scenario is O(N * log(N)), while the space complexity is O(N) as a result of recursion.

6. Using an Auxiliary Array:

The method functions by gathering data from the linked list, arranging it with the help of an auxiliary array, and then generating a fresh linked list based on the sorted data.

Advantages: Maintains the initial format and is straightforward to comprehend.

Cons: It may not be suitable for large lists.

Time and Space Complexity: The time complexity for the sorting algorithm is O(N * log(N)), where N represents the number of elements being sorted. In terms of space complexity, it is O(N) because of the auxiliary array utilized during the sorting process.