Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

# Flatten a Multi-level Linked List (Depth wise)

## Introduction

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
{
// 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)

if (next)

return node;
}

// Function to print a linked list
{
{
}

}

// 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);

// Flatten list and Print Flatten list

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)

if(next!=null)

return node;
}

// Function to print a linked list
public static void printFlattenNodes(Node 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[]) {
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);

}
}

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

After reading about the Flatten a Multi-level Linked List (Depth wise), are you not feeling excited to read/explore more articles on the topic of DSA? Don't worry; Coding Ninjas has you covered. To learn, see Construct the Full K-ary Tree from its Preorder TraversalRegular and Bipartite graphs, and Planar and Non-Planar Graphs.

Recommended Problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Coding!

Topics covered
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Solution
3.1.
Algorithm
3.2.
Code Implementation
4.