1.
Introduction
1.1.
Problem Statement
1.2.
Explanation of the problem
1.3.
Sample Example
2.
Brute-force Approach
2.1.
Steps of the approach
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of the approach
3.2.
Implementation in C++
3.3.
Complexity Analysis
4.
4.1.
What is a queue?
4.2.
What is a priority queue?
4.3.
What is a struct?
5.
Conclusion
Last Updated: Mar 27, 2024

Vidhi Singh
0 upvote

## Introduction

Data Structures and Algorithms are the backbones of a technical Interview. To test that, interviewers often put up programming questions in front of the candidate.

### Problem Statement

You are given a multi-level Linked List. You are supposed to write a function that converts the multi-level liked list into a linear set of sorted values. Also, each Linked List is sorted, so the result should also be sorted(in ascending order).  Note that set is not the Data Structure: set. It is used to refer to a group of elements.

### Explanation of the problem

The question mentions multi-level Linked List. Its structure looks something like this:

Every node has two pointers - the next pointer and the below pointer.

Now, we will be given such a Linked List and we are supposed to convert it into a linear set of sorted values. But, the catch here is that each linked list in itself is sorted and after flattening into a sorted set also, it should be sorted.

### Sample Example

For example, if the multi-level Linked List is :

Then, the Singly Linked List should be:

We hope the question is clear now. Let us now move to the solution to the problem.

## Brute-force Approach

A very simple idea that may hit your mind at that time can be of merging two sorted Linked Lists. (You can try this question before moving forward.).

The catch here is that you keep merging them until there is just one Linked List left.

For the example considered above, it would be something like this:

Step 1:

Step 2:

Step 3:

Step 4:

### Steps of the approach

2. Make the result of that the first Linked List.
3. Repeat 1 and 2 until only one Linked List is left.

### Implementation in C++

The C++ code for the above approach is as follows:

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

class Node    //Nodes
{
public:
int value;
Node *next;
Node *below;
Node(int num)
{
value=num;
next=NULL;
below=NULL;
}
};

Node* insert(Node *head,int num)    //Inserting a new node
{

Node* new_node=new Node();

new_node->value=num;
new_node->next=NULL;

}

Node* Merge(Node* first, Node* second)    //Merging two Linked List
{
if(first==NULL)
return second;

if(second==NULL)
return first;

Node* ans;

if(first->value<second->value)
{
ans=first;
ans->below=Merge(first->below,second);
}
else
{
ans=second;
ans->below=Merge(first, second->below);
}
ans->next=NULL;
return ans;
}

Node* converting(Node* head)    //Converting to linear sorted set
{

}

{
cout<<"The Linear set is: "<<" ";
while(t!=NULL)
{
cout<<t->value<<" ";
t=t->below;
}
cout<<endl;
}

int main()
{

return 0;
}``````

Input:

``````head=insert(head, 7);

Output:

``The Linear set is:  5 7 11 12 18 19 21 24 26 29 31 ``

### Complexity Analysis

Time Complexity: O(n*n*m)

Now, we are merging Linked Lists, so merging lists takes O(m) complexity, where â€˜mâ€™ is the number of elements in each list. Let there be â€˜nâ€™ Linked Lists, so the total time is O(m)*O(2+3+...n). Using the formula(1+2+...+n=(n*(n+1)/2)), time complexity is O(m*n*n).

Space Complexity: O(n*m)

For space, as we are using recursion, a recursion stack will be maintained, that will take O(m*n).

## Optimized Approach

Now, let us think of a more optimized approach. Our end result should be a sorted set of values. So, what we can do is push all the nodes into a priority list(priority by value in ascending order) and then form a Linked List from those values.

First, push all the first nodes. Now extract each node, and print all the below nodes in the order.
Since it is a priority queue, the node extracted will have the least value of all the nodes in the priority queue.

This is a very direct explanation of the approach. It will become more clear if we break it into steps.

### Steps of the approach

1. Insert the first nodes of all the main Linked Lists into the priority list.
2. Extract node
3. Print node
4. Go to â€˜belowâ€™ and if it is not NULL, then insert that in the priority queue.
5. If the priority queue is not empty, repeat 2, 3, and 4. Else, END

### Implementation in C++

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

class Node //Nodes of the Linked List
{
public:
int value;
Node* next;
Node* below;

Node(int num)
{
value=num;
next=NULL;
below=NULL;
}
};

struct comp  //for ascending priority
{
bool operator()(Node* a,Node* b)
{
return a->value>b->value;
}
};

{
priority_queue<Node*,vector<Node*>,comp> p;
{
}

while(!p.empty())
{
auto k=p.top();
p.pop();
cout<<k->value<<" ";
if (k->below)
p.push(k->below);
}

}

int main()
{
return 0;
}``````

Input:

``````Node* head=new Node(5);
below_t->below=new Node(7);
t->next=new Node(11);
t=t->next;
below_t=t;
below_t->below=new Node(12);
below_t->below->below=new Node(18);
t->next=new Node(19);
t=t->next;
below_t=t;
below_t->below=new Node(21);
below_t->below->below=new Node(24);
below_t->below->below->below=new Node(26);
t->next=new Node(29);
t=t->next;
below_t=t;
below_t->below=new Node(31);

cout<<"The sorted set is: ";
cout << endl;``````

Output:

``The sorted set is: 5 7 11 12 18 19 21 24 26 29 31  ``

### Complexity Analysis

Time Complexity: O(m*n*log(n))

Since a priority queue has been used, so time complexity is O(m*n*log(n)) where â€˜nâ€™ are the number of nodes in the main Linked List and â€˜mâ€™ is the nodes below the main nodes.

Space Complexity: O(n)

Space complexity is O(n) as the size of the priority queue will never be more than n(â€˜nâ€™ is the number of nodes in the main linked list.)

#### What is a queue?

A queue is a data structure that follows the rule of FIFO(First In First Out), that is the most recent element will be accessed first.

#### What is a priority queue?

A priority queue is a data structure that assigns a particular priority to the elements for retrieval. The FIFO property is followed but for the priority of the element.

#### What is a struct?

struct is a keyword of C and C++ that is used to declare a structure. It is a collection of variables that may or may not be of the same data types.