Flatten a Multi-level Linked List (Depth wise)

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;
}

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

Run Code

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;
}
}

You can also try this code with Online Java Compiler

Run Code

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 Traversal, Regular and Bipartite graphs, and Planar and Non-Planar Graphs.

Recommended Problems -

• Flattening A Linked List
• Sorted Doubly Linked List
• Linked List Cycle ii
   

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System 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!