Flattening a Linked List

In this article, we are going to study about the logic behind the flattening of linked list and we also going to build a code in the C++ to flatten a given linked list. In this challenge, we are given a linked list with the right and down pointer nodes. Main linked list pointer is located at right node. The secondary linked list is for the node at the bottom of the list.

Approach for the program

We can use merge sort to combine all the sub-lists into a single list because each sub-list in the linked list is in sorted order.

The following steps make up this algorithm:

• A two-pointer to a dummy node should be created. As we merge the linked list, one pointer is used to maintain track of the dummy node and the second pointer is utilized to advance.
• Using the merging algorithm of the merge sort, select any two sub-linked lists and run through the list to combine them.
• Return the final list after combining all sub-lists into one.

C++ Example for flattening a linked list

// C++ program for flattening a
// Linked List
#include <bits/stdc++.h>
using namespace std;


// Link list node
class Node
{
	public:
	int data;
	Node *right, *down;
};


Node* head = NULL;


Node* merge(Node* a, Node* b)
{
	
	if (a == NULL)
		return b;


	
	if (b == NULL)
		return a;


	
	Node* result;


	if (a->data < b->data)
	{
		result = a;
		result->down = merge(a->down, b);
	}


	else
	{
		result = b;
		result->down = merge(a, b->down);
	}
	result->right = NULL;
	return result;
}


Node* flatten(Node* root)
{
	// Base Cases
	if (root == NULL ||
		root->right == NULL)
		return root;


	// Recur for list on right
	root->right = flatten(root->right);


	// Now merge
	root = merge(root, root->right);


	// Return the root
	// It will be in turn merged
	// with its left
	return root;
}


// Utility function to insert a node at
// beginning of the linked list
Node* push(Node* head_ref, int data)
{
	// Allocate the Node &
	// Put in the data
	Node* new_node = new Node();


	new_node->data = data;
	new_node->right = NULL;


	// Make next of new Node as head
	new_node->down = head_ref;


	// Move the head to point to
	// new Node
	head_ref = new_node;


	return head_ref;
}
void printList()
{
	Node* temp = head;
	while (temp != NULL)
	{
		cout << temp->data << " ";
		temp = temp->down;
	}
	cout << endl;
}
int main()
{
	/* Create the following linked list
		5 -> 10 -> 19 -> 28
		| |	 |	 |
		V V	 V	 V
		7 20 22 35
		|		 |	 |
		V		 V	 V
		8		 50 40
		|			 |
		V			 V
		30			 45
	*/
	head = push(head, 30);
	head = push(head, 8);
	head = push(head, 7);
	head = push(head, 5);


	head->right = push(head->right, 20);
	head->right = push(head->right, 10);


	head->right->right =
	push(head->right->right, 50);
	head->right->right =
	push(head->right->right, 22);
	head->right->right =
	push(head->right->right, 19);


	head->right->right->right =
	push(head->right->right->right, 45);
	head->right->right->right =
	push(head->right->right->right, 40);
	head->right->right->right =
	push(head->right->right->right, 35);
	head->right->right->right =
	push(head->right->right->right, 20);


	// Flatten the list
	head = flatten(head);


	printList();
	return 0;
}

Output:

5 7 8 10 19 20 20 22 30 35 40 45 50

The flattened linked list it above has all of its components arranged in alphabetical order. Two techniques, which are further described in this article, can flatten a linked list.

Time Complexity

The formula is O(N * N * M), where N is the number of nodes in the primary linked list and M is the number of nodes in a single sub-linked list.

Explanation of time complexity

• Two lists are being combined at once.
• The time required will be O(M+M) = O after combining the first two lists (2M).
• After that, we will merge a second list with the one above it (3M).
• Then we shall combine another list, making time equal to O(3M + M).
• The process of combining lists will continue until all lists have been combined.
• O(2M + 3M + 4M +.... N*M) = (2M + 3M + 4M +.... N*M) * M will be the total amount of time required.
• Time = O(((N * N + N - 2) * M/2) using the arithmetic sum formula.
• For a large value of N, the preceding expression generally equals O(N * N * M).