Flatten a multi-level linked list (Depth wise)

In this article, we will learn how we can flatten the list either horizontally using the next pointers or vertically using the down pointers. let’s try to understand the logic to flatten a multilevel linked list.

How to flattening a linked list

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.

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 flattening a linked list, 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 for flattening a linked list

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

• 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 to flatten a multilevel linked list

• 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 to flatten a multilevel linked list

## Code Implementation of flattening a linked list

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node *next;
    struct Node *down;
};
 
// Flattens a multi-level linked list depth wise

struct Node* flattenList(struct Node* node)
{
    // Base case
    if (node == NULL)
        return NULL;
 
    // To keep track of last visited node
    // (NOTE: This is static)
    static struct Node* last;
    last = node;
 
    // Store next pointer
    struct Node *next = node->next;
 
    // If down list exists, process it first
    // Add down list as next of current node
    if (node->down)
       node->next = flattenList(node->down);
 
    // If next exists, add it after the next
    // of last added node
    if (next)
       last->next = flattenList(next);
 
    return node;
}
 
// Utility method to print a linked list
void printFlattenNodes(struct Node* head)
{
    while (head)
    {
    printf("%d ", head->data);
    head = head->next;
    }
    
}
 
// Utility function to create a new node
struct Node* newNode(int new_data)
{
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = new_node->down = NULL;
    return new_node;
}
 
// Driver code
int main()
{
    // Creating above example list
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->down = newNode(7);
    head->next->down->down = newNode(9);
    head->next->down->down->down = newNode(14);
    head->next->down->down->down->down
                                     = newNode(15);
    head->next->down->down->down->down->next
                                     = newNode(23);
    head->next->down->down->down->down->next->down
                                      = newNode(24);
    head->next->down->next = newNode(8);
    head->next->down->next->down = newNode(16);
    head->next->down->next->down->down = newNode(17);
    head->next->down->next->down->down->next
                                      = newNode(18);
    head->next->down->next->down->down->next->next
                                      = newNode(19);
    head->next->down->next->down->down->next->next->next
                                      = newNode(20);
    head->next->down->next->down->down->next->next->next->down
                                      = newNode(21);
    head->next->down->next->next = newNode(10);
    head->next->down->next->next->down = newNode(11);
 
    head->next->down->next->next->next = newNode(12);
 
    // Flatten list and print modified list
    head = flattenList(head);
    printFlattenNodes(head);
 
    return 0;
}

#include <bits/stdc++.h>
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<<endl;
}

/* Main driver function */
int main()
{
	Node* head = createNode(1);
	head->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;
}

class Node
{
    int data;
    Node next,down;
    Node(int data)
    {
        this.data=data;
        next=null;
        down=null;
    }
}
class Flatten 
{

    static Node last;

    // Flattens a multi-level linked list depth wise
    public static Node flattenList(Node node)
    {
        if(node==null)
            return null;

        // To keep track of last visited node
        // (NOTE: This is static)
        last = node;

        // Store next pointer
        Node next = node.next;

        // If down list exists, process it first
        // Add down list as next of current node
        if(node.down!=null)
            node.next = flattenList(node.down);

        // If next exists, add it after the next
        // of last added node
        if(next!=null)
            last.next = flattenList(next);

        return node;
    }
    public static void printFlattenNodes(Node head)
    {
        Node curr=head;
        while(curr!=null)
        {
            System.out.print(curr.data+" ");
            curr = curr.next;
        }
        
    }
    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(1);
        head.next = new Node(2);
        head.next.next = new Node(5);
        head.next.down = new Node(6);
        head.next.down.down = new Node(35);
        head.next.down.down.down = new Node(28);
        head.next.down.down.next= new Node(4);
        head.next.down.down.next.down= new Node(0);
        head.next.down.down.next.next = new Node(3);
        
        System.out.println("The linked list after flattening");
        head = flattenList(head);
        printFlattenNodes(head);
    }
}

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

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

So, in this blog, we have explained how we can flatten a multilevel linked list. The intuition of considering it as a binary tree will help to solve this problem easily. To brush up your skills more on a linked lists,feel free to solve them at Linked List.

## FAQs related to flattening a linked list

**1. What is a multilevel linked list?**
Multilevel Linked List is a 2D data structure that comprises several linked lists and each node in a multilevel linked list has a next and child pointer.

**2. Can merge sort work for linked lists?**
It works on a linked list in the same way it works on an array.

**3. Which sorting algorithm is not suitable for the linked list?**
Using a linked list binary search will take O(n) time. So binary search is inefficient with linked lists.