The Linked list is one of the most important data structures to learn when preparing for interviews. A good understanding of Linked Lists could come in handy during a coding interview.

Flatten a Multi-level Linked list is one of the most frequently asked interview questions.

In this blog, we will go through the Problem Statement of the question, learn how to solve this problem, and discuss the code in different programming languages.

Problem Statement

We have given a linked list containing the next and down pointers. The next pointer, as expected, points to the next node. On the other hand, the down pointer points to a node that we assume is present in the downward direction of a node.

Our goal is to flatten a linked list containing next and down pointers while also ensuring that the down pointer is always processed before the next at each node.

In other words, we need to convert it into a normal linked list that contains only the next pointer.

Example

Input:

Output: The flattened linked list will look like the below.

Note that node 6 will appear before 12 because we are processing down pointer before the next pointer.

Solution

I hope you have a basic understanding of what we need to do to solve the problem. We will solve this problem using Recursion.

Letâ€™s discuss the Algorithm to solve this problem.

Algorithm

Letâ€™s discuss the algorithm step by step.

1.) Return NULL if the node is NULL. It is the base case.

2.) Save the current node's next node (used in step 4).

3.) Flatten the list recursively. Keep track of the last visited node while flattening so the next list can be linked.

4.) Recursively Flatten the next list (from the pointer stored in step 2) and attach it after the last visited node in a recursive manner.

5.) After performing all the above steps, we get the Flattened Linked List.

Time Complexity: O(N), where N is the number of nodes in a linked list.

Since we are recursively moving through each node, the time complexity will depend on the number of nodes in the linked list.

Space Complexity: O(1), since we are not using any extra space to store nodes.

But there will be an Auxilary Space Complexity of O(N) due to the Recursive Stack that can store a maximum of up to N nodes.

Code Implementation

C++:

// C++ program to flatten a multilevel linked list - Depth Wise
#include <bits/stdc++.h>
using namespace std;
// A Linked List Node
struct Node
{
int data;
struct Node *next;
struct Node *down;
};
// Flattens a multi-level linked list depth wise
Node* flattenLinkedList(Node* node)
{
// Base case
if (node == NULL)
return NULL;
// To keep track of last visited node
static Node *previous;
previous = node;
// Store next pointer
Node *next = node->next;
if (node->down)
node->next = flattenLinkedList(node->down);
if (next)
previous->next = flattenLinkedList(next);
return node;
}
// Function to print a linked list
void printFlattenList(Node* head)
{
while (head)
{
printf("%d ", head->data);
head = head->next;
}
}
// Function to create a new node
Node* newNode(int new_data)
{
Node* new_node = new Node;
new_node->data = new_data;
new_node->next = new_node->down = NULL;
return new_node;
}
// Driver code
int main()
{
// Creating above example list
Node* head = newNode(5);
head->next = newNode(10);
head->next->next = newNode(12);
head->next->next->next = newNode(9);
head->next->down = newNode(6);
head->next->down->down = newNode(11);
head->next->down->down->down = newNode(14);
head->next->next->down = newNode(15);
// Flatten list and Print Flatten list
head = flattenLinkedList(head);
printFlattenList(head);
return 0;
}

Output:

We are running it for the example that we have taken previously.

We can see we are getting the required flattened linked list.

Java:

// Java program to flatten a multilevel linked list - Depth Wise
public class FlattenList {
static Node last;
// Flattens a multi-level linked list depth wise
public static Node flattenLinkedList(Node node)
{
if(node==null)
return null;
// To keep track of prev visited node
prev = node;
// Store next pointer
Node next = node.next;
if(node.down!=null)
node.next = flattenLinkedList(node.down);
if(next!=null)
prev.next = flattenLinkedList(next);
return node;
}
// Function to print a linked list
public static void printFlattenNodes(Node head)
{
Node curr=head;
while(curr!=null)
{
System.out.print(curr.data+" ");
curr = curr.next;
}
}
// Function to create a new node
public static Node push(int newData)
{
Node newNode = new Node(newData);
newNode.next =null;
newNode.down = null;
return newNode;
}
public static void main(String args[]) {
Node head=new Node(5);
head.next = new Node(10);
head.next.next = new Node(12);
head.next.next.next = new Node(9);
head.next.down = new Node(6);
head.next.down.down = new Node(11);
head.next.down.down.down = new Node(14);
head.next.next.down = new Node(15);
head = flattenList(head);
printFlattenNodes(head);
}
}
//Node of Multi-level Linked List
class Node
{
int data;
Node next,down;
Node(int data)
{
this.data=data;
next=null;
down=null;
}
}

Output:

We are running it for the example that we have taken previously.

We can see we are getting the required flattened linked list.

Frequently Asked Questions

What is a Linked List?

A linked list is a linear data structure in which the elements are not stored in contiguous memory locations. A linked list's elements are connected via pointers.

Types of Linked List?

There are four main types of Linked List:-

1.) Singly Linked List

2.) Doubly Linked List

3.) Circular Linked List

4.) Doubly Circular Linked List

What is the main difference between an Array and a Linked list?

In Array, the elements are stored in contiguous memory locations, while in a linked list, the elements are not necessarily stored in contiguous memory locations.

What is the key difference between a Singly Linked list and a Multi-level Singly linked list?

The singly linked list only contains the next pointer, while the Multi-level singly linked list contains the next and down pointer.

What are the applications of the Linked list?

Some of the applications of the Linked list are:-

1.) Polynomial Manipulation representation.

2.) Addition of long positive integers.

3.) Representation of sparse matrices.

4.) Addition of long positive integers.

Conclusion

In this article, we have extensively discussed how to flatten a multi-level linked list depth-wise, its algorithm, space and time complexity, and implementation in different programming languages.