Flatten a Multi-Level Linked List Editorial

Practice Problem Link: Flatten A Multi-Level Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a linked list structure, where each node has two pointers:

• next: points to an identical node towards the right.
• down: points to an identical node towards the bottom.

Only the topmost node can have a non-NULL next pointer.

This gives us a set of vertical linked lists and a horizontal linked list with the head nodes of the vertical lists.

Also, all vertical lists are sorted.

Your task is to flatten the lists into a single linked list, which should also be sorted.

Naive Approach

• Since all the columns are sorted, we can store the pointer of the first element of each column in an array.
• Now find the minimum element from the array and add it to the answer. Store the next pointer of the same column from which the last element was picked in the array.
• Repeat the above step until the end of all the columns are reached to get the answer.

Analysis

• Time Complexity: O(Total Nodes * No. of Columns)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;
	ListNode* down;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
		this->down = NULL;
	}
};
*/

ListNode* flattenTheLinkedList(ListNode* root) {
	vector<ListNode*> columns;
	ListNode* currentNode = root;
	ListNode* head = new ListNode(INT_MAX);
	int i = 0, index;
	while(currentNode != NULL) {
		columns.push_back(currentNode);
		if (head->data > currentNode->data) {
			head->data = currentNode->data;
			index = i;
		}
		i++;
		currentNode = currentNode->next;
	}
	columns[index] = columns[index]->down;
	currentNode = head;
	while (1) {
		int endOfList = 1;
	    index = - 1;
		ListNode* currentMin = new ListNode(INT_MAX);
		for (int i = 0; i < columns.size(); i++) {
			if(columns[i] == NULL) {
				continue;
			}
			if(columns[i]->data < currentMin->data) {
				currentMin = columns[i];
				index = i;
				endOfList = 0;
			}
		}
		if (endOfList == 1) {
			break;
		}
		currentNode->next = currentMin;
		currentNode = currentMin;
		columns[index] = columns[index]->down;
	}
	return head;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;
	ListNode down;

	ListNode(int data) {
		this.data = data;
		this.next = null;
		this.down = null;
	}
}
**/

class Solution {
	ListNode flattenTheLinkedList(ListNode root) {
		ListNode currentNode = root;
		int totalLength = 0;
		while (currentNode != null) {
			totalLength++;
			currentNode = currentNode.next;
		}
		ListNode[] columns = new ListNode[totalLength];
		currentNode = root;
		ListNode head = new ListNode(Integer.MAX_VALUE);
		int i = 0, index = 0;
		while(currentNode != null) {
			columns[i] = currentNode;
			if (head.data > currentNode.data) {
				head.data = currentNode.data;
				index = i;
			}
			i++;
			currentNode = currentNode.next;
		}
		columns[index] = columns[index].down;
		currentNode = head;
		while (true) {
			int endOfList = 1;
			index = - 1;
			ListNode currentMin = new ListNode(Integer.MAX_VALUE);
			for (i = 0; i < columns.length ; i++) {
				if(columns[i] == null) {
					continue;
				}
				if(columns[i].data < currentMin.data) {
					currentMin = columns[i];
					index = i;
					endOfList = 0;
				}
			}
			if (endOfList == 1) {
				break;
			}
			currentNode.next = currentMin;
			currentNode = currentMin;
			columns[index] = columns[index].down;
		}
		return head;
	}
}

Another Approach

The idea is to merge each vertical list with its next vertical list after flattening the next vertical list recursively to form a new sorted and flattened list.

Analysis

• Time Complexity: O(Total Nodes * (Total Columns)2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;
	ListNode* down;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
		this->down = NULL;
	}
};
*/
ListNode* mergeTwoList(ListNode* list1, ListNode* list2) {
	if (list1 == NULL && list2 == NULL) return NULL;
	if (list1 == NULL) {
		return list2;
	}
	if (list2 == NULL) {
		ListNode* result = list1;
		result->next = mergeTwoList(list1->down, NULL);
		result->down = NULL;
		return result;
	}
	ListNode* result;
	if (list1->data < list2->data) {
		result = list1;
		result->next = mergeTwoList(list1->down, list2);
	}
	else {
		result = list2;
		result->next = mergeTwoList(list1, list2->next);
	}
	result->down = NULL;
	return result;
}
ListNode* flattenTheLinkedList(ListNode* root) {
	if (root == NULL) return root;
	return mergeTwoList(root, flattenTheLinkedList(root->next));
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;
	ListNode down;

	ListNode(int data) {
		this.data = data;
		this.next = null;
		this.down = null;
	}
}
**/

class Solution {
	ListNode mergeTwoList(ListNode list1, ListNode list2) {
		if (list1 == null && list2 == null) return null;
		if (list1 == null) {
			return list2;
		}
		if (list2 == null) {
			ListNode result = list1;
			result.next = mergeTwoList(list1.down, null);
			result.down = null;
			return result;
		}
		ListNode result;
		if (list1.data < list2.data) {
			result = list1;
			result.next = mergeTwoList(list1.down, list2);
		}
		else {
			result = list2;
			result.next = mergeTwoList(list1, list2.next);
		}
		result.down = null;
		return result;
	}

	ListNode flattenTheLinkedList(ListNode root) {
		if (root == null) return root;
		return mergeTwoList(root, flattenTheLinkedList(root.next));
	}
}

Optimal Approach

The efficient approach is based on the naive approach only, but instead of using an array to store the topmost elements of each column, a Min heap is used so that finding the minimum element can be done in logarithmic time instead of linear time.

Analysis

• Time Complexity: O(Total Nodes * log(No. of Columns))
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;
	ListNode* down;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
		this->down = NULL;
	}
};
*/
struct cmp{
	bool operator() (ListNode* a,ListNode* b) const{
		return a->data < b->data;
	}
};
ListNode* flattenTheLinkedList(ListNode* root) {
	multiset<ListNode*, cmp> columns;
	ListNode* currentNode = root;
	int i = 0, index;
	while(currentNode != NULL) {
		columns.insert(currentNode);
		currentNode = currentNode->next;
	}
	ListNode* head = *columns.begin();
	columns.erase(columns.begin());
	currentNode = head;
	if (currentNode->down != NULL) {
		columns.insert(currentNode->down);
	}
	while (!columns.empty()) {
		ListNode* currentMin = *columns.begin();
		columns.erase(columns.begin());
		currentNode->next = currentMin;
		currentNode = currentMin;
		if (currentMin->down != NULL) {
			columns.insert(currentMin->down);
		}
	}
	return head;
}