Introduction

Before getting started, let’s understand what multilayer or multilevel linked list data structure is. A multilevel linked list is a 2D data structure composed of multiple linked lists, with each node having a next and child pointer. Pointers are used to connect all the elements.

As in a linked list, the first node is the Head, as shown above. The value of the head is NULL if the multilevel linked list is empty. Each node in a list is made up of at least three components:
- Data
- Pointer to the next node.
- Pointer to the child node.
Each node of the multi-level linked list is represented as:

In the above diagram, the pointer to the next points to the null as there are no other nodes. Likewise, there are no further child nodes; the pointer to the child is pointing to the null.
Let’s get started now with the problem:
Flatten a multilevel linked list
This article aims to flatten a multilevel linked list into a single-level linked list, as shown below.

You are given the head of the first level of the list. Flatten the list so that all the nodes appear in a single-level linked list. You need to flatten the list so that all nodes at the first level should come first, then nodes at the second level, etc.
Examples
Input:

Output:-

Explanation:
The problem specifies that the list must be flattened level by level. The solution's concept is to start from the first level and process all nodes one by one. If a node has a child, we append the child to the end of the list; otherwise, we keep moving. All next-level nodes will be appended after the first level has been analysed. The appended nodes go through the same procedure.
It is recommended to try the stated problem on your own before jumping to the solution.
Let’s discuss the approach for the same:
The simple method is to keep a pointer 'TAIL' that initially refers to the end of the first level. (a level that contains a head). And the challenge now is to link all of the nodes so that they are only accessed by the 'TAIL' through the next parameter. Take another pointer, 'CURR,' which points to the current node and traverse the list until it reaches the end (null). If a node has a child, then we append the child at the end of the list(i.e., TAIL->next = CURR.child). The exact process will be followed for the appended nodes.
Algorithm
Step 1:- Take the “TAIL” pointer, pointing to the end of the first level.
Step 2:- Take the “CURR” pointer, which will point to the current node in the list; initially, it will point to the Head.
Step 3:- Repeat the below procedure until the (CURR ! = null).
Step 3.1:- If the current node has a child, then:
3.1.1-Append the new child at the end i.e. to the TAIL:
TAIL->next = CURR->child
3.1.2-Find the last node of the new child list and update the “TAIL”:
tmp = cur->child;
while (tmp->next != NULL)
tmp = tmp->next;
tail = tmp;
If current node does not have a child then:
Move to the next node:
CURR = CURR->next
Let’s look at the Implementation to Illustrate the above algorithm:
Implementation in C++
struct Node
{
// linked list Node has three parameters
// data, next pointer and child pointer
int data;
struct Node *next;
struct Node *child;
};
// C++ program for flatten the multilevel linked list
#include <bits/stdc++.h>
using namespace std;
//Linked list Node has three parameters
// data, next pointer and child pointer
struct Node
{
int data;
Node *next;
Node *child;
};
//this function will take the head of level1 and will flatten the multilevel list
void flattenMultilevel(Node *head)
{
Node *temp;
// if the list is empty
if (head == NULL)
{
return;
}
// if the list is not empty
Node *tail = head;
// Updating the tail( or end) of the level1 list
while (tail->next != NULL)
{
tail = tail->next;
}
// Initially CURR will point to the Head
Node *curr = head;
//Traverse level1 list
while (curr != NULL)
{
//If current node has child
if (curr->child)
{
//Appending the child at the end of current list( TAIL)
tail->next = curr->child;
//Updating the tail to the new last node
temp = curr->child;
while (temp->next)
{
temp = temp->next;
}
tail = temp;
}
// Increment the CURR pointer
curr = curr->next;
}
}
void insertAtBeginning(Node **head, int dataToBeInserted)
{
Node *curr = new Node;
// make a new node with this data and next pointing to NULL
curr->data = dataToBeInserted;
curr->next = NULL;
// if list is empty then set the current formed node as head of list
if (*head == NULL)
*head = curr;
else
{
// make the next of the current node point to the present head and make the current node the new head
curr->next = *head;
*head = curr;
}
// O(1) constant time
}
// display function for printing the flatten list
void display(Node **head)
{
Node *temp = *head;
//till the list ends (NULL marks ending of list)
while (temp != NULL)
{
if (temp->next != NULL)
cout << temp->data << " ->";
else
cout << temp->data;
//move to next node
temp = temp->next;
}
cout << endl;
}
int main()
{
Node *result = NULL;
Node *level1 = NULL;
//initial list has no elements
insertAtBeginning(&level1, 11);
insertAtBeginning(&level1, 7);
insertAtBeginning(&level1, 12);
insertAtBeginning(&level1, 5);
insertAtBeginning(&level1, 10);
Node *level2 = NULL;
insertAtBeginning(&level2, 2);
insertAtBeginning(&level2, 17);
insertAtBeginning(&level2, 13);
insertAtBeginning(&level2, 20);
insertAtBeginning(&level2, 4);
Node *level3 = NULL;
insertAtBeginning(&level3, 16);
// level1 has data = 10 -> child = level2 has data = 4
level1->child = level2;
// level2 2nd node = 20
level2->next->child = level3;
flattenMultilevel(level1);
cout << "Flattend List is" << endl;
display(&level1);
return 0;
}
Output
Flattend List is
10 ->5 ->12 ->7 ->11 ->4 ->20 ->13 ->17 ->2 ->16
Time Complexity:- O(n), where n is the number of nodes in the given list. Since every node is visited at most twice.
Auxiliary Space:- O(1), as we are not using any additional space.
PICTORIAL REPRESENTATION

