Flatten a Linked List

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.  

In this article, we will discuss a question on the topic of Linked List.

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 

1. ApplyLinked List Merge Sort on the first two Linked Lists 
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* head =NULL; 
Node* insert(Node *head,int num)    //Inserting a new node
{
     
    Node* new_node=new Node();
 
    new_node->value=num;
    new_node->next=NULL;
 
    new_node->below=head;
 
    head=new_node;
 
    return head;
}

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
{ 
    if(head==NULL||head->next==NULL)
        return head;
 
    head->next=converting(head->next);
 
    head=Merge(head,head->next);
 
    return head;
}

void printLinkedList()    //Printing the Linked List
{
    Node* t=head; 
    cout<<"The Linear set is: "<<" ";
    while(t!=NULL)
    {
        cout<<t->value<<" ";
        t=t->below;
    }
    cout<<endl;
}

int main()
{
     
        return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

head=insert(head, 7);
head=insert(head, 5);
 
head->next=insert(head->next,18);
head->next=insert(head->next,12); 
head->next=insert(head->next,11);
 
head->next->next = insert(head->next->next,26);
head->next->next = insert(head->next->next,24);
head->next->next = insert(head->next->next,21); 
head->next->next = insert(head->next->next,19);
 
head->next->next->next = insert(head->next->next->next,31);
head->next->next->next = insert(head->next->next->next,29); 
  
head=converting(head);
 
printLinkedList();

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).