Flatten a multi-level linked list (Depth wise)

Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

Problem Statement

The linked list that we have studied typically has only one pointer, i.e., a next pointer, which points to the next node in the linked list.

But, here in this problem, we have a linked list with 2 pointers named next and down.

  • The next pointer points normally to the next node.
  • But the down pointer points to a node that we assume is present in a node’s downward direction.

Our task is to flatten a linked list containing next and down pointers, and also we must make sure that we always process the down pointer before next at every node.

Problem Statement Understanding

According to the problem statement, we have a linked list with 2 pointers named next and down, and we need to convert it to the normal linked list that we have studied earlier, i.e., we need to move nodes that are being pointed by the down pointer to next making all down pointers NULL, but also we need to keep in mind that we process down pointer before processing next pointer.

An alternate way to understand it even more is to imagine it as a binary tree (as shown in the image below).

  • And now, all we need to do is to visit each node such that when we are at a current node then we need to first explore the nodes pointed by down pointer and when the list with current node's down pointer is flattened completely, then we have to move towards node pointed by next pointer and perform the same task there also.

If say our given linked list is:

  • In this case, our flattened list will be :

Now, we just need to perform a preorder traversal of the given linked list recursively, where down nodes will be flattened before the next nodes.

Approach

I hope that you got a basic idea of what we need to do to solve the problem.

  • The approach will be recursive; we have to consider the given list as a binary tree and traverse it in a preorder fashion.
  • We have to first flatten the down nodes recursively and then the next nodes.
  • Since we need to flatten the list:
    • So, we need to visit nodes present in the downward direction first.
    • We will keep a global pointer previous that would store the address of the current node to keep track of the last visited node.
    • And then, in each recursive call, we would be storing the next pointer and then call the recursive function for the down pointer first, and then will do the same for the next pointer afterwards.
  • After performing the above steps, our list will get flattened.

Algorithm

  • Base case: If the node is NULL, we do not need to do anything and we just return from recursion.

  • Otherwise, store the address of the current node in a global variable previous to keep track of the last visited node.

  • Store the current node’s next node in a variable next_node because at first, we will be processing down nodes, and not storing current node’s next will lead to loss of the next node and all its connected nodes.

  • Then, we need to check whether the down node of the current node exists or not.

    • If it exists, we recursively call our function for the down node and flatten down nodes first and connect with current->next.
    • current->next = flatten_linked_list(current->down).
  • Then we check if the next node next_node (saved in step 3) exists or not.

    • If it exists, we again call the recursive function to flatten the linked list and connect it with previous->next.
    • previous->next = flatten_linked_list(next_node)
  • Finally, we return current.

Dry Run

![](https://blog.prepbytes.com/wp-content/uploads/2021/10/p_1.png)

![](https://blog.prepbytes.com/wp-content/uploads/2021/10/p_2.png)

![](https://blog.prepbytes.com/wp-content/uploads/2021/10/p_3.png)

Code Implementation

#include 
using namespace std;

/* Structure of a linked list node */
struct Node
{
    int data;
    struct Node *next;
    struct Node *down;
};

/* Using this function we will be creating a new list node */
Node* createNode(int new_data)
{
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = new_node->down = NULL;
    return new_node;
}

/* The global node as discussed in step 2 */
Node *previous = NULL;

/* Using this function we will be flattening the multilevel linked list */
Node* flatten_linked_list(Node* current)
{
	// Base case
	if (current == NULL)
		return NULL;

	previous = current;// storing current node address as
	//discussed in step 2

	Node *next_node = current->next;// storing current
	// node’s next as discussed in step 3 

	// if down pointer of current node is not null then, we
	// process it first
	if (current->down != NULL)
	current->next = flatten_linked_list(current->down);
	// If the next node that we discussed in step 3 is not null
	// then we process it
	if (next_node != NULL)
	previous->next = flatten_linked_list(next_node);

	return current;
}

/* Using this function we will be printing the content of the linked list */
void print_linked_list(Node* head)
{
	while (head != NULL)
	{
		cout<<(head->data)<<" ";
		head = head->next;
	}
	cout<next = createNode(2);
	head->next->next = createNode(5);
	head->next->down = createNode(6);
	head->next->down->down = createNode(35);
	head->next->down->down->down = createNode(28);
	head->next->down->down->next = createNode(4);
	head->next->down->down->next->down = createNode(0);
	head->next->down->down->next->next = createNode(3);
	
	head = flatten_linked_list(head);
	cout<<"The linked list after flattening: ";
	print_linked_list(head);
	return 0;
}

Output

The linked list after flattening: 1 2 6 35 28 4 0 3 5

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

So, in this blog, we have tried to explain how you can Flatten a multi-level linked list in depthwise order. The intuition of considering it as a binary tree will help to solve this problem easily. If you want to practise more questions on linked list, feel free to solve them at Linked List.

Previous post Flatten Binary Tree To Linked List
Next post Applications of Linked List Data Structure

Leave a Reply

Your email address will not be published. Required fields are marked *