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
Code Implementation
#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; struct Node *down; }; // Flattens a multilevel 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 multilevel 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 number of nodes in the list.
[forminator_quiz id=”5386″]
So, in this blog, we have tried to explain how you can Flatten a multilevel 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.