Flatten A Linked List
You are given a linked list containing N nodes, where every node in the linked list contains two pointers, first one is ‘NEXT’ which points to the next node in the list and the second one is ‘CHILD’ pointer to a linked list where the head is this node. And each of these child linked lists is in sorted order.

Your task is to flatten this linked such that all nodes appear in a single layer or level while the nodes should maintain the sorted order.

For example:

The given linked list is -

So your output should be 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 12 → 20 → null.

Note:

The flattened list will be printed using the bottom pointer instead of the next pointer. The value of any node in the linked list will not be equal to -1.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of the test case contains ‘N’ which represents the number of next-nodes in the linked list. The description of the next N lines is as follows- Each line contains space-separated integers which are the child nodes of the head linked list and each line ends with -1 to indicate that the sublist is over. Thus, -1 will never be a linked list element.

Output format :

For each test case, return the head node of the final linked list. The output of each test case will be printed in a separate line.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Flatten A Linked List

You are given a linked list containing N nodes, where every node in the linked list contains two pointers, first one is ‘NEXT’ which points to the next node in the list and the second one is ‘CHILD’ pointer to a linked list where the head is this node. And each of these child linked lists is in sorted order.

Your task is to flatten this linked such that all nodes appear in a single layer or level while the nodes should maintain the sorted order.

For example:

The given linked list is -

So your output should be 

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 12 → 20 → null.

Note:

The flattened list will be printed using the bottom pointer instead of the next pointer.

The value of any node in the linked list will not be equal to -1.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of the test case contains ‘N’ which represents the number of next-nodes in the linked list.

The description of the next N lines is as follows-

Each line contains space-separated integers which are the child nodes of the head linked list and each line ends with -1 to indicate that the sublist is over. Thus, -1 will never be a linked list element.

Output format :

For each test case, return the head node of the final linked list. The output of each test case will be printed in a separate line.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 100
1 <= C <= 20
1 <= data <= 1000

Time Limit: 1sec

Accepted Answer

Brute Force

The idea is to use an extra array to first store all the elements of the linked list and then sort the array and finally put those elements back into the linked list and return.

Declare an array ‘Answer’ to store the elements of the linked list.
Run a while loop till the next of the linked list reaches NULL.
- Add the current pointer data to Answer.
- Inside this loop, traverse the CHILD nodes of the current node.In every iteration of this loop add the data of every node to Answer.
- After this loop, move to the next node of the current node..
After these loops sort the array and add the array elements to the new linked list and return it.

Space Complexity: O(n^2)Explanation:

O(N * K), where ‘N’ denotes the size of the linked list and ‘K’ is the average number of child nodes for each of the N nodes.

Since we are using an array to store all the nodes of the linked list, and we are creating a new linked list to again store all the nodes, so the effective space complexity would be O(N * K) + O(N * K) = O(N * K).

Time Complexity: O(nlogn)Explanation:

O((N * K) * (log(N * K))), where ‘N’ denotes the size of the linked list and ‘K’ is the average number of child nodes for each of the N nodes.

Since we are taking all nodes data in an array and then sorting it so the total complexity will O(N * K) + O((N * K) * log(N * K))

C++ (g++ 5.4)

/*

    Time Complexity: O((N * K) * (log(N * K)))

    Space complexity: O(N * K)



    Where ‘N’ denotes the size of the linked list and ‘K’ is the average number of child nodes for each of the N nodes. 

*/



#include



Node* flattenLinkedList(Node* root) 

{

	vector answer ;



	// Traverse the linkedlist and add all the nodes to the array

	while (root != NULL) 

	{

		answer.push_back(root->data);

		Node *temp = root;



		// Add all child nodes

		while (temp->child != NULL) 

		{

			answer.push_back(temp->child->data);

			temp = temp->child;

		}

		root = root->next;

	}



	sort(answer.begin(), answer.end());



	Node *head = NULL;

	Node *tail = NULL;



	// Create new linked list

	for (int i = 0; i < answer.size(); ++i) 

	{

		Node *newNode = new Node(answer[i]);

		if (head == NULL) 

		{

			head = newNode;

		} 

		else 

		{

			tail->child = newNode;

		}

		tail = newNode;

	}

	return head;

}

Java (SE 1.8)

/*

    Time Complexity: O((N * K) * (log(N * K)))

    Space complexity: O(N * K)



    Where 'N' denotes the size of the linked list and 'K' is the average number of child nodes for each of the N nodes. 

*/

import java.util.ArrayList;

import java.util.Collections;



public class Solution {

	public static Node flattenLinkedList(Node root) {

		ArrayList answer = new ArrayList();



		// Traverse the linked and add all the nodes to list

		while (root != null) {

			answer.add(root.data);

			Node temp = root;



			// Add all child nodes

			while (temp.child != null) {

				answer.add(temp.child.data);

				temp = temp.child;

			}

			root = root.next;

		}

		Collections.sort(answer);



		Node head = null;

		Node tail = null;



		// Create new linked list

		for (int i = 0; i < answer.size(); ++i) {

			Node newNode = new Node(answer.get(i));



			if (head == null) {

				head = newNode;

			} else {

				tail.child = newNode;

			}

			tail = newNode;

		}

		return head;

	}

}

Python (3.5)

'''

    Time Complexity: O((N * K) * (log(N * K)))

    Space complexity: O(N * K)



    Where 'N' denotes the size of the linked list and 'K' is the average number of child nodes for each of the N nodes. 

'''



class Node:

    def __init__(self, data):



        self.data = data

        self.next = None

        self.child = None



    def __del__(self):

        if(self.next):

            del self.next





def flattenLinkedList(root) :



	answer = []



	# Traverse the linkedlist and add all the nodes to the array

	while (root != None) :

	

		answer.append(root.data)

		temp = root



		# Add all child nodes

		while (temp.child != None) :

		

			answer.append(temp.child.data)

			temp = temp.child

		

		root = root.next

	



	answer.sort()



	head = None

	tail = None



	# Create new linked list

	for i in range(len(answer)):

	

		newNode = Node(answer[i])

		if (head == None) :

		

			head = newNode

		 

		else :

		

			tail.child = newNode

		

		tail = newNode

	

	return head

Accepted Answer

Using Priority Queue

The idea is to use the given situation that each sublist is sorted and there are a total of N nodes that means there are N sorted sublists. So the idea is to sort the whole thing.

First of all, we need to add the nodes that are on the first horizontal level that are heads of the sublist to the priority queue say pq.
Now run a while loop until this queue goes empty.
- Now take out the smallest element from the priority queue that is just pop the element from the priority queue.
- Insert the next child node pointed by the current node (if the child node is not null).
- And repeat these above two steps until the queue goes empty.
- Now add the popped nodes to the linked list.
- Here we will not create new nodes for making the list instead we just change the links i.e. we will make a new node headOne and initially we will make it equal to the first popped node.
- After that, we will keep on adding the nodes by changing the links.
Finally, return the linked list obtained.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the size of the linked list

Since we are using a priority queue to store the top horizontal nodes and at any instant heap will not contain more than N nodes..

Time Complexity: O(n^2logn)Explanation:

O( log(N) * (N * K)), where 'N’ denotes the size of the linked list and ‘K’ is the average number of child nodes for each of the N nodes.

Since, every node in the linkedlist is traversed once and log(N) is the time taken to min-heapify the queue so the total complexity will be O(N * log(N)) + O(((N * K) - N) * log(N)) = O( log(N) * (N * K))

Python (3.5)

'''

    Time Complexity: O( log(N) * (N * K))

    Space complexity: O(N)



    Where 'N' denotes the size of the linked list and 'K' is the average number of child nodes for each of the N nodes. 

'''



class Node:

    def __init__(self, data):



        self.data = data

        self.next = None

        self.child = None



    def __del__(self):

        if(self.next):

            del self.next



def merge(first, second) :



	# If the first is None return second

	if (first == None) :



		return second

	

	# If the second is None return first

	if (second == None) :

	

		return first

	





	if (first.data < second.data) :

	

		merged = first

		merged.child = merge(first.child, second)

	 

	else :

	

		merged = second

		merged.child = merge(first, second.child)

	

	return merged





def flattenLinkedList(head) :



	if (head == None or head.next == None):

	

		return head

	



	# Recur on next node

	head.next = flattenLinkedList(head.next)



	# Merge with the current

	head = merge(head, head.next)



	return head

Java (SE 1.8)

/*

    Time Complexity: O( log(N) * (N * K))

    Space complexity: O(N)



    Where 'N' denotes the size of the linked list and 'K' is the average number of child nodes for each of the N nodes. 

*/

public class Solution {

	public static Node merge(Node first, Node second) {

		// If the first is null return second

		if (first == null) {

			return second;

		}



		// If the second is null return first

		if (second == null) {

			return first;

		}



		Node merged;



		if (first.data < second.data) {

			merged = first;

			merged.child = merge(first.child, second);

		} else {

			merged = second;

			merged.child = merge(first, second.child);

		}

		return merged;

	}



	public static Node flattenLinkedList(Node head) {

		if (head == null || head.next == null) {

			return head;

		}



		// Recur on next node

		head.next = flattenLinkedList(head.next);



		// Merge with the current

		head = merge(head, head.next);



		return head;

	}

}

Accepted Answer

In-place

The idea is to merge the linked list in place and merge it recursively with the current flattened list. Basically, we are traversing through the linked list and each time, we are merging the two-child lists into one. We will repeat this process until we are left with only one final linked list containing all the nodes. In short, we repeatedly merge the current list with the already flattened list.

Make a function mergeLists which will take two lists as parameters.
- Basically, this function is merging two sorted lists as we do in merge sort of linked list.
- Inside this function check for the null nodes i.e. if the first list is empty then return the second list else return the first list.
- Now compare the data of both the list if the data of first st list is lesser than second then recurse on the child of first
- Else recurse on the child of the second list.
- Finally, return the node.
Now in the flattenLinkedList function here also recurse on the next pointer of the list and after that call the 'mergeList' functions (to merge the current flattened linked list with already flattened one) and finally return head.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the size of the linked list.

Since for every call on a horizontal node each child sublist is called so the stack in recursion will always at most have N stacks .

Time Complexity: O(n^2)Explanation:

O(N * K), where ‘N’ denotes the size of the linked list and ‘K’ is the average number of child nodes for each of the N nodes.

Since, every next-node and every child node in the linkedlist is traversed only once, the final complexity would be O(N * K).

C++ (g++ 5.4)

/*

    Time Complexity: O(N * K)

    Space complexity: O(N)



    Where 'N' denotes the size of the linked list and 'K' is the average number of child nodes for each of the N nodes->

*/



Node *merge(Node *first, Node *second)

{

    // If the first is NULL return second

    if (first == NULL)

    {

        return second;

    }



    // If the second is NULL return first

    if (second == NULL)

    {

        return first;

    }



    Node *merged = NULL;



    if (first->data < second->data)

    {

        merged = first;

        merged->child = merge(first->child, second);

    }

    else

    {

        merged = second;

        merged->child = merge(first, second->child);

    }

    merged->next = nullptr;

    return merged;

}



Node *flattenLinkedList(Node *head)

{

    if (head == NULL || head->next == NULL)

    {

        return head;

    }



    // Recur on next node

    head->next = flattenLinkedList(head->next);



    // Merge with the current

    head = merge(head, head->next);



    return head;

}

Java (SE 1.8)

/*

    Time Complexity: O(N * K)

    Space complexity: O(N)



    Where 'N' denotes the size of the linked list and 'K' is the average number of child nodes for each of the N nodes. 

*/

public class Solution {

	public static Node merge(Node first, Node second) {

		// If the first is null return second

		if (first == null) {

			return second;

		}



		// If the second is null return first

		if (second == null) {

			return first;

		}



		Node merged;



		if (first.data < second.data) {

			merged = first;

			merged.child = merge(first.child, second);

		} else {

			merged = second;

			merged.child = merge(first, second.child);

		}

		return merged;

	}



	public static Node flattenLinkedList(Node head) {

		if (head == null || head.next == null) {

			return head;

		}



		// Recur on next node

		head.next = flattenLinkedList(head.next);



		// Merge with the current

		head = merge(head, head.next);



		return head;

	}

}

Python (3.5)

'''

    Time Complexity: O(N * K)

    Space complexity: O(N)



    Where 'N' denotes the size of the linked list and 'K' is the average number of child nodes for each of the N nodes. 

'''



class Node:

    def __init__(self, data):



        self.data = data

        self.next = None

        self.child = None



    def __del__(self):

        if(self.next):

            del self.next



def merge(first, second) :



	# If the first is None return second

	if (first == None) :



		return second

	

	# If the second is None return first

	if (second == None) :

	

		return first

	





	if (first.data < second.data) :

	

		merged = first

		merged.child = merge(first.child, second)

	 

	else :

	

		merged = second

		merged.child = merge(first, second.child)

	

	return merged





def flattenLinkedList(head) :



	if (head == None or head.next == None):

	

		return head

	



	# Recur on next node

	head.next = flattenLinkedList(head.next)



	# Merge with the current

	head = merge(head, head.next)



	return head

Your task is to flatten this linked such that all nodes appear in a single layer or level while the nodes should maintain the sorted order.

For example:

Note:

Input format :

Output format :

Note:

Constraints:

Top Morgan Stanley Technology Analyst interview questions & answers

Popular interview questions of Technology Analyst

Top HR questions asked in Morgan Stanley Technology Analyst