Table of contents
1.
Introduction
2.
Flatten a multilevel linked list
2.1.
Examples
2.2.
Algorithm
2.3.
Implementation in C++
2.4.
PICTORIAL REPRESENTATION
3.
Frequently Asked Questions
3.1.
How do you flatten a doubly linked list?
3.2.
What is a singly linked list?
3.3.
How do the doubly linked lists work?
3.4.
What is a multi-level linked list?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Flatten a multilevel linked list

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Flatten a Multilevel Linked List

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. 

illustrative image

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:

  1. Data
  2. Pointer to the next node.
  3. Pointer to the child node.

Each node of the multi-level linked list is represented as:

illustrative image

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.

illustrative image

 

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:

illustrative image

 

Output:-

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;
}
You can also try this code with Online C++ Compiler
Run Code

Output

Flattend List is
10 ->5 ->12 ->7 ->11 ->4 ->20 ->13 ->17 ->2 ->16
You can also try this code with Online C++ Compiler
Run Code

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

illustrative image

 

illustrative image

Frequently Asked Questions

How do you flatten a doubly linked list?

You can flatten the linked list by doing a preorder traversal, popping nodes from a stack, and pushing on the next node before any child nodes, guaranteeing that the nodes are visited in a preorder sequence.

What is a singly linked list?

A single linked list is a form of unidirectional linked list, meaning that it can only be traversed in one way, from head to last node (tail). A linked list's elements are referred to as nodes. A single node includes data and a pointer to the next node, which aids in the list's structure.

How do the doubly linked lists work?

A doubly linked list is a linked list in which each node contains two links and holds data. The first link leads to the previous node in the list, while the second leads to the next node. The two links allow us to move through the list in both directions.

What is a multi-level linked list?

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 of the components. A pointer represents a multilevel linked list to the initial node of the linked list.

Conclusion

To conclude, we learned about multilevel linked lists and how to flatten them into single lists. We described a naïve method in which we implemented the stack and multi-level linked list data structures. There is another technique to make the conversion, which is to use recursion. Stay tuned for the next post, in which we will go through the various ways. Do practise if you want to make your coding adventure a success.

Don't be still, Ninja; we have many great articles that will propel you to the next level and make you stand out from the crowd.

Thanks for reading!

Happy Learning Ninja!

Live masterclass