Abstract / Summary

Flatten a multilevel doubly linked list into a single level doubly linked list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 63% (700k+ submissions).

Typical patterns to solve this problem:

• Depth First Search
• Doubly Linked List
• Linked List
• Recursion

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class that converts a multilevel doubly linked list into a single-level doubly linked list. The conversion proceeds in two phases: first, a depth-first traversal collects all node values into a plain Python list; second, a new list of Node objects is created and linked together to form the flattened structure. The code is concise and leverages Python’s built-in list operations and comprehensions to keep the logic straightforward.

Core Traversal Logic

The add method performs a recursive depth-first walk of the original multilevel list. It returns a flat list of values in the order they should appear after flattening.

def add(self, root):
    if not root:
        return []
    return [root.val] + self.add(root.child) + self.add(root.next)

The method first checks whether the current root reference is None. When the list is empty, it returns an empty list, which serves as the base case for the recursion. For a non-empty node, the method constructs a new list consisting of three concatenated parts:

1. A one-element list containing the current node’s value.
2. The result of recursively processing the child pointer, which represents the sub-list that should be inserted immediately after the current node.
3. The result of recursively processing the next pointer, which continues the traversal at the same level.

Because Python’s list concatenation creates a new list each time, the recursion naturally yields a flat sequence of values that respects the required ordering: parent, then its child subtree, then the sibling nodes.

Edge Cases Handled by add

When the input root is None, the early return produces an empty list, ensuring that the recursion terminates correctly without attempting to access attributes on a null reference. The same base case also covers leaf nodes whose child and next attributes are None; the recursive calls on those attributes each return an empty list, so the concatenation reduces to just the current node’s value.

Construction of the Flattened List

The flatten method orchestrates the overall transformation. It first gathers all values using add, then builds a new doubly linked list from those values.

def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
    if not head:
        return None

    all = self.add(head)
    size = len(all)

    result = [Node(all[i], None, None, None) for i in range(size)]

    for i in range(size):
        if i > 0:
            result[i].prev = result[i-1]
        if i < size - 1:
            result[i].next = result[i+1]

    return result[0]

The method begins with a guard clause that returns None when the supplied head is None, mirroring the behavior of add for an empty input. After obtaining the flat list of values (all), it records the number of elements (size).

A list comprehension creates a fresh Node instance for each value, initializing all pointer fields (prev, next, child) to None. This approach avoids repeated calls to a constructor inside a loop and benefits from Python’s internal optimizations for list comprehensions.

The subsequent for loop walks through the newly created nodes once, establishing the prev and next links. The conditional checks ensure that the first node never receives a prev reference and the last node never receives a next reference, thereby correctly handling the boundaries of the list. Because the loop touches each node a constant number of times, the linking phase runs efficiently.

Finally, the method returns the first node in the result array, which now serves as the head of the fully flattened doubly linked list.

Edge Cases Handled by flatten

If the original list consists of a single node without children, add returns a list with one element, size becomes 1, and the list comprehension creates a solitary Node. The linking loop runs once, but both conditional branches are skipped, leaving the node’s prev and next as None. The method then returns this node, correctly representing a flattened list of length one.

When the original structure contains multiple levels of nesting, the recursive add method guarantees that all descendant values are placed in the correct order before the sibling nodes are processed. Consequently, the flatten method receives a correctly ordered value list and produces a linear doubly linked list that reflects the intended flattening semantics.

Performance Optimizations Observed

The code makes deliberate use of Python’s built-in features to keep the runtime overhead low. The recursion in add builds the final value list through a series of concatenations; while each concatenation creates a new list, the overall number of concatenations is proportional to the number of nodes, and Python’s memory management for small lists is highly optimized.

The list comprehension that constructs the Node objects is a single pass that avoids the overhead of repeatedly invoking append. By pre-allocating the entire list of nodes, the implementation sidesteps the need for dynamic resizing that would occur with incremental insertion.

Linking the nodes in a separate loop ensures that each node’s prev and next pointers are set exactly once. The conditional checks inside the loop are simple integer comparisons, which are inexpensive. This separation of node creation and pointer wiring keeps the two phases clean and allows the interpreter to optimize each phase independently.

Overall, the design balances readability with efficient use of Python’s data structures, resulting in a solution that performs the flattening operation with minimal auxiliary overhead.

Imagine you have a big toy train that tracks its cars in a special way. Some cars have a cargo hold underneath them that has its own line of cars, and some cars are hooked directly to the one in front.

The code starts by walking through all the train cars, looking inside every cargo hold and following every hook to find every single car in the whole train. It makes a list of all the pieces it finds, lining them up in the right order from start to finish. Once it has that orderly list, it creates a bunch of brand new train cars based on the pieces it found.

After making the new cars, it goes through the line one by one and connects them. It tells each car to hold the hand of the car in front of it and the car behind it. By the time it finishes, it has built a simple, straight train where every car follows the next one in a perfect row, just like a long, flat snake made of train cars.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java			Python		TS
	WalkCCC	C++	Java			Python
	leetcode.ca	C++	Java			Python
	LeetcodeHelp	C++	Java			Python
	Progiez	C++	Java			Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune		Java
	lkwq007					Python
	MacJim	C++
	suxrobGM				C#
	varunu28		Java
	wisdompeak	C++
	yuanliu666						Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	Java
lkwq007	Python
MacJim	C++
suxrobGM	C#
varunu28	Java
wisdompeak	C++
yuanliu666	Kotlin

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality