Flatten a Multilevel Doubly Linked List

Medium

Amazon

5 views

Topics:

Linked ListsRecursionStacks

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6]

Example 2:

Input: head = [1,2,null,3] Output: [1,3,2]

Example 3:

Input: head = [] Output: []

Constraints:

The number of Nodes will not exceed 1000.
1 <= Node.val <= 10^5

Write a function to flatten the given multilevel doubly linked list.

Flatten a Multilevel Doubly Linked List

Medium

Amazon

5 views

Topics:

Linked ListsRecursionStacks

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6]

Example 2:

Input: head = [1,2,null,3] Output: [1,3,2]

Example 3:

Input: head = [] Output: []

Constraints:

The number of Nodes will not exceed 1000.
1 <= Node.val <= 10^5

Write a function to flatten the given multilevel doubly linked list.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the nodes in the list contain any data type other than integers?
Is it possible for the child list to point back to a node in the parent list, creating a cycle?
If a node has both a next and a child pointer, which should be processed first during flattening?
What should be returned if the input head is null or the list is empty?
Is it guaranteed that the doubly linked list is properly formed (e.g., next and prev pointers are consistent within each level)?

Brute Force Solution

Approach

The brute force approach tackles this problem by systematically exploring every single possible arrangement of the linked list. We essentially try out all combinations to flatten the structure, without any initial smart guesses. This means it checks every possible path regardless of whether it's promising or not.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the list.
If you find a place where there's a 'child' list branching off, try following that child list all the way to its end.
Once you reach the end of the child list, attach it back to the main list and continue from where you branched off.
Alternatively, don't follow the child list and continue along the main list.
Keep a record of all the different ways you could flatten the list by choosing to follow or not follow each child branch.
Once you've explored every possible combination of following or not following the child branches, you will have a bunch of different flattened lists.
Go through all the flattened lists you've created and pick the one that is the correct flattened order according to the problem's requirements.

Code Implementation

class Node:
	def __init__(self, value):
		self.value = value
		self.prev = None
		self.next = None
		self.child = None

def flatten_multilevel_doubly_linked_list_brute_force(head):
	possible_flattened_lists = []

	def explore_combinations(current_node, current_list):
		if not current_node:
			possible_flattened_lists.append(current_list[:])
			return

		# Option 1: Don't follow the child and continue with the next node
		explore_combinations(current_node.next, current_list + [current_node.value])

		# Option 2: Follow the child if it exists
		if current_node.child:
			child_head = current_node.child
			# Traverse the entire child list
			child_list = []
			child_current = child_head
			while child_current:
				child_list.append(child_current.value)
				child_current = child_current.next

			# Add the child list to the current combination and move to the next node
			explore_combinations(current_node.next, current_list + [current_node.value] + child_list)

	# Start exploring combinations from the head
	explore_combinations(head, [])

	# Brute-force: Find the correct flattened list by checking each combination
	# In a real scenario, we would define what constitutes a correct solution
	# For now, assume the first combination is always valid.
	# A better implementation would check and validate each combination.
	if possible_flattened_lists:
		correct_flattened_list = possible_flattened_lists[0]
		return correct_flattened_list

	return []

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible combinations of traversing the main list or descending into a child list whenever one is encountered. In the worst-case scenario, every node has a child. For each node, we have two choices: either flatten the child list first, or continue with the main list. Since there could be n nodes where each one has a child list, this makes 2*2*2... (n times) or 2^n possible traversals. Therefore the time complexity is O(2^n).

Space Complexity

O(2^N) – The brute force approach explores every possible combination of following or not following child branches. This implies a decision tree where each node represents a choice (follow child or not), and the depth of the tree could be proportional to the number of nodes with children, which in the worst case could be N, where N is the number of nodes in the list. Because we explore all possible paths, we are implicitly creating a space to store all flattened lists resulting from these combinations. In the worst case, where every node has a child, there would be 2^N possible combinations to store. Thus, the space complexity is O(2^N).

Optimal Solution

Approach

The best way to flatten the list is to walk through it, fixing up the connections as you go. Whenever you find a child list, you insert it into the main list and remember where the child list ends so you can reconnect things correctly later.

Here's how the algorithm would work step-by-step:

Start at the beginning of the main list.
Go through the list node by node.
If a node has a child list, take that child list and insert it right after the current node in the main list.
Remember the last node of the child list. You'll need it later to reconnect things.
Once the child list is inserted, connect the last node of the child list to the node that originally came after the node with the child.
After reconnecting, keep going through the main list from where you left off. Continue until you've reached the end of the main list.

Code Implementation

class Node:
    def __init__(self, value, previous_node=None, next_node=None, child_node=None):
        self.value = value
        self.previous_node = previous_node
        self.next_node = next_node
        self.child_node = child_node

def flatten_multilevel_linked_list(head):
    current_node = head

    while current_node:
        if current_node.child_node:
            # Found a child, need to insert it
            child_head = current_node.child_node
            child_tail = child_head

            # Find the tail of the child list.
            while child_tail.next_node:
                child_tail = child_tail.next_node

            next_node = current_node.next_node

            # Splice in the child list
            current_node.next_node = child_head
            child_head.previous_node = current_node

            # Need to relink the original list
            if next_node:
                child_tail.next_node = next_node
                next_node.previous_node = child_tail

            current_node.child_node = None # Remove child pointer after merging

            current_node = current_node.next_node

        else:
            current_node = current_node.next_node

    return head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each node of the multilevel doubly linked list exactly once. When a child list is encountered, it's inserted into the main list by adjusting pointers. The process of inserting a child list requires traversing its nodes once, but each node is visited and modified only a constant number of times throughout the entire algorithm's execution. Therefore, the time complexity is directly proportional to the number of nodes in the flattened list, which we define as n, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm operates in-place by modifying the existing linked list structure. It only requires a few constant extra variables to keep track of the current node and the tail of the child list when reconnecting. The space used does not depend on the number of nodes N in the linked list. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty list	Return null immediately as there's nothing to flatten.
List with only one node and no child	Return the single node list as is since it's already flattened.
List with only one node and a child that is a null list	Return the single node list, ignoring the null child list.
Deeply nested children lists (high recursion depth)	Iterative approach avoids stack overflow issues associated with deeply nested recursive calls.
Circular references or cycles in the child/next pointers	Iterative approach prevents infinite loops by not revisiting nodes already processed during flattening.
A node with both 'next' and 'child' being null	Algorithm handles this by continuing to the next node in list.
Large number of nodes in the list (scalability)	Iterative approach has a time complexity of O(N), making it efficient for large lists.
Child node points to a node already visited on the main level	Iterative approach correctly splices in the child list without creating cycles.