Flatten a Multilevel Doubly Linked List

📋

Problem

Imagine you have a complex file system where folders can contain files and other folders nested arbitrarily deep. You want to list all files in a single linear order, flattening the hierarchy.

You are given a doubly linked list where in addition to the next and previous pointers, each node may have a child pointer, which may point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure. Flatten the list so that all the nodes appear in a single-level, doubly linked list. The nodes should appear in the order they are encountered in a depth-first traversal.

1 ≤ Number of nodes ≤ 10^5Node values are integersChild pointers may be nullThe list may be empty (head is null)

Edge cases: Empty list (head is null) → output is nullList with no child pointers → output is the same listList where every node has a child → output is a deeply nested flattened list

</>

IDE

def flatten(head: 'Node') -> 'Node':public Node flatten(Node head)Node* flatten(Node* head)function flatten(head)

def flatten(head):
    # Write your solution here
    pass

class Solution {
    public Node flatten(Node head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

Node* flatten(Node* head) {
    // Write your solution here
    return nullptr;
}

function flatten(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Flattened list missing child nodes or child lists appended at the end onlyGreedy approach that flattens child lists only after traversing next nodes✅ Flatten child lists immediately when encountered before continuing with next nodes

Wrong: Infinite loop or repeated nodes in outputNot clearing child pointers after flattening causing repeated processing✅ Set node.child = null after flattening its child list

Wrong: Broken doubly linked list with incorrect prev pointersNot updating prev pointers when linking child lists✅ Set child.prev = current node and child's last next.prev = original next node

Wrong: Function crashes or returns non-null on empty inputNo base case for null head input✅ Add base case: if head is null, return null immediately

Wrong: Function modifies single node or returns null incorrectlyIncorrect handling of single node with no child✅ Return head immediately if no child or next nodes

✓

Test Cases

Make sure your solution handles empty and single-node lists correctly.

Watch out for greedy approaches and pointer update errors.

Focus on algorithmic complexity and avoid nested loops.

t1_01basic

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":7,"prev":null,"next":{"val":8,"prev":null,"next":{"val":11,"prev":null,"next":{"val":12,"prev":null,"next":{"val":9,"prev":null,"next":{"val":10,"prev":null,"next":{"val":4,"prev":null,"next":{"val":5,"prev":null,"next":{"val":6,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Starting at head 1, traverse next nodes until 3, then go down child list starting at 7, flattening recursively, then continue with 4, 5, 6.

💡 Think about depth-first traversal of the multilevel list.

💡 Use a stack or recursion to process child lists before continuing with next nodes.

💡 Link child list between current node and next node, then nullify child pointer.

Why it failed: Incorrect flattening order or missing child nodes. Fix by ensuring child lists are inserted immediately after current node before continuing with next nodes. This is the canonical example test.

✓ Correctly flattened the multilevel doubly linked list preserving DFS order.

t1_02basic

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":{"val":5,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Node 3 has a child list 4->5 which is flattened between 3 and null.

💡 Check if child lists are inserted immediately after their parent node.

💡 Ensure child pointers are set to null after flattening.

💡 Update prev pointers correctly when linking child lists.

Why it failed: Child list not inserted or child pointer not cleared. Fix by linking child list after current node and nullifying child pointer.

✓ Child list correctly flattened and linked.

t2_01edge

Input{"head":null}

Expectednull

⏱ Performance - must finish in 2000ms

Empty list input should return null.

💡 Check if input head is null before processing.

💡 Return null immediately if list is empty.

💡 Avoid dereferencing null pointers.

Why it failed: Function crashes or returns non-null on empty input. Fix by adding base case: if head is null, return null.

✓ Correctly handles empty list input.

t2_02edge

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":null,"child":null}

⏱ Performance - must finish in 2000ms

Single node with no child remains unchanged after flattening.

💡 Test with minimal input of one node.

💡 Ensure function returns the same node if no child exists.

💡 Check that no pointers are incorrectly modified.

Why it failed: Function modifies single node or returns null incorrectly. Fix by returning head immediately if no child or next nodes.

✓ Correctly returns single node unchanged.

t2_03edge

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":5,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Every node has a child, resulting in a deeply nested flattened list preserving DFS order.

💡 Test deep nesting of child pointers.

💡 Ensure recursive or stack-based DFS fully traverses all levels.

💡 Verify child pointers are cleared after flattening.

Why it failed: Partial flattening or missing nested children. Fix by recursively flattening all child lists before continuing.

✓ Correctly flattens deeply nested child lists.

t3_01corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":5,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Greedy approach that flattens child lists only when next is null fails here; correct DFS order requires flattening child of 1 before continuing to 2.

💡 Beware of flattening child lists only at the end of next nodes.

💡 Use DFS to flatten child lists immediately after current node.

💡 Insert child list between current node and next node, not after traversing next nodes.

Why it failed: Greedy flattening after next traversal causes incorrect order. Fix by flattening child list immediately when found, before continuing next.

✓ Correct DFS order flattening, not greedy.

t3_02corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":null,"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Confusing 0/1 flattening with unbounded: child list must be flattened once per node, not repeatedly or infinitely.

💡 Ensure child lists are flattened exactly once per node.

💡 Avoid loops or repeated flattening of the same child.

💡 Clear child pointer after flattening to prevent reprocessing.

Why it failed: Repeated flattening or infinite loops due to not clearing child pointer. Fix by setting child to null after flattening.

✓ Child pointer cleared and flattened exactly once.

t3_03corner

Input{"head":[1]}

Expected{"val":1,"prev":null,"next":{"val":2,"prev":null,"next":{"val":3,"prev":null,"next":{"val":4,"prev":null,"next":null,"child":null},"child":null},"child":null},"child":null}

⏱ Performance - must finish in 2000ms

Off-by-one errors in linking prev and next pointers cause broken doubly linked list after flattening.

💡 Carefully update prev pointers when linking child lists.

💡 Check that child's prev points to current node after insertion.

💡 Verify next pointers of last child node link to original next node.

Why it failed: Prev or next pointers not updated correctly causing broken links. Fix by setting child.prev = current and child's last next.prev = original next.

✓ All prev and next pointers correctly updated.

t4_01performance

Input{"head":[1]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 nodes linked linearly with no children; O(n) expected to complete within 2s.

💡 Use iterative or recursive DFS with O(n) time complexity.

💡 Avoid repeated traversals or nested loops causing O(n^2).

💡 Use stack or recursion carefully to avoid stack overflow.

Why it failed: TLE due to O(n^2) or exponential complexity. Fix by using O(n) DFS or iterative stack approach.

✓ Algorithm runs in O(n) time and passes performance test.

Practice

1. You are given a singly linked list where each node contains an additional pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both the next and random pointer structure. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

B. Use a hash map to store original-to-copy node mappings and create the copy in two passes.

C. Use a recursive function with memoization to copy nodes and their random pointers.

D. Traverse the list multiple times, copying nodes and random pointers separately without extra data structures.

Solution

1. Step 1: Understand the problem constraints

   The problem requires copying a complex linked list with random pointers efficiently.

2. Step 2: Identify the optimal approach

   Interleaving copied nodes within the original list allows assigning random pointers without extra space, then separating the lists restores the original and creates the copy.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interleaving nodes achieves O(n) time and O(1) space [OK]

Hint: Interleaving nodes avoids extra space for mapping [OK]

Common Mistakes:

• Assuming recursion is always optimal
• Using extra hash maps increases space complexity
• Trying multiple traversals without mapping fails random pointer assignment

2. What is the amortized time complexity of the visit, back, and forward operations in the two stacks approach for browser history, assuming n total operations?

medium

A. O(1) amortized per operation since each URL is pushed and popped at most once per stack

B. O(n) total for all operations combined, but O(1) worst-case per operation

C. O(log n) per operation due to stack resizing costs

D. O(n) per operation because each visit may clear the forward stack

Solution

1. Step 1: Analyze push/pop operations per URL

   Each URL is pushed once onto back_stack and popped at most once to forward_stack, and vice versa.

2. Step 2: Calculate amortized cost

   Since each URL moves between stacks a limited number of times, total operations over n steps average to O(1) per operation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) is standard for two stacks navigation [OK]

Hint: Each URL moves between stacks only a few times [OK]

Common Mistakes:

• Assuming clearing forward stack is O(n) per visit
• Confusing amortized with worst-case
• Ignoring stack push/pop costs

3. What is the time and space complexity of the optimal in-place odd-even linked list rearrangement algorithm for a list of length n?

medium

A. Time: O(n), Space: O(1) because each node is visited once and rearranged in-place

B. Time: O(n log n), Space: O(1) due to sorting nodes by index parity

C. Time: O(n), Space: O(n) due to auxiliary lists for odd and even nodes

D. Time: O(n^2), Space: O(1) because of nested pointer updates

Solution

1. Step 1: Identify loop iterations

   The while loop advances even and odd pointers through the list, each node visited once -> O(n) time.

2. Step 2: Analyze space usage

   No extra data structures are created; rearrangement is done by pointer manipulation -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space is standard for in-place linked list rearrangement [OK]

Hint: One pass with two pointers -> O(n) time, no extra lists -> O(1) space [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2) time
• Confusing auxiliary space with recursion stack

4. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?

medium

A. O(nk), because each group reversal takes O(k) and there are n/k groups.

B. O(n), because each node is visited and reversed exactly once.

C. O(n log k), because reversing each group involves log k steps due to pointer updates.

D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

1. Step 1: Analyze group reversal cost

   Each group of k nodes is reversed in O(k) time.

2. Step 2: Count total groups and total nodes processed

   There are approximately n/k groups, so total time is O(k * n/k) = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each node is processed once during reversal [OK]

Hint: Total nodes processed once -> O(n) time [OK]

Common Mistakes:

• Multiplying n by k incorrectly
• Assuming log k factor in reversal
• Ignoring that groups partition the list

5. Suppose the problem is modified so that the linked list nodes can be reused across parts (i.e., nodes can appear in multiple parts). Which of the following changes to the algorithm correctly handles this variant?

hard

A. No changes needed; the original algorithm already supports node reuse by splitting normally.

B. Modify the algorithm to skip cutting pointers and just record start nodes for each part, allowing overlap.

C. Use a hash map to track nodes already assigned and avoid duplicates during splitting.

D. Instead of cutting the list, create new nodes for each part to allow reuse without modifying the original list.

Solution

1. Step 1: Understand node reuse requirement

   Nodes can appear in multiple parts, so original list must remain intact.

2. Step 2: Evaluate algorithm changes

   Original algorithm cuts pointers, destroying original list structure. To allow reuse, new nodes must be created for each part.

3. Step 3: Discard other options

   Skipping cutting pointers causes overlapping parts but does not create separate nodes. Hash map tracking is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Creating new nodes preserves original list and allows reuse [OK]

Hint: Node reuse requires copying nodes, not pointer cutting [OK]

Common Mistakes:

• Assuming original algorithm supports reuse
• Trying to reuse nodes without copying
• Overcomplicating with tracking structures