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 and asked to reorder it so that all nodes at odd indices appear before nodes at even indices, preserving the relative order within each group. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Using a stack to push odd nodes and then pop them to reorder the list

B. Sorting the list based on node values and then merging odd and even indexed nodes

C. Using two pointers to rearrange nodes in-place by linking odd and even nodes separately and then concatenating

D. Using a hash map to store nodes by index parity and reconstructing the list from the map

Solution

1. Step 1: Understand problem constraints

   The problem requires reordering nodes by their position (odd/even indices) without extra space and in linear time.

2. Step 2: Evaluate approaches

   Only the two-pointer in-place rearrangement achieves O(n) time and O(1) space by relinking nodes without extra data structures.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is standard for odd-even linked list rearrangement [OK]

Hint: Two pointers rearranging nodes in-place is optimal [OK]

Common Mistakes:

• Thinking sorting or extra data structures are needed
• Assuming extra space is acceptable for optimal

2. You are given a singly linked list and an integer k. The task is to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the remaining nodes at the end should remain as is. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use a recursive approach that reverses k nodes at a time and recurses on the rest, relying on call stack for reversal.

B. Apply a dynamic programming approach to store reversed sublists and combine them for the final result.

C. Iteratively traverse the list, reversing each group of k nodes using a helper function, and reconnect groups with pointer manipulation.

D. Use a greedy approach that reverses nodes whenever possible without checking group boundaries.

Solution

1. Step 1: Understand problem constraints

   The problem requires reversing nodes in groups of k, preserving the order of leftover nodes if fewer than k remain.

2. Step 2: Evaluate approaches

   Recursive approach (A) uses extra stack space and risks overflow; DP (B) is not applicable; greedy (D) fails on partial groups. Iterative with helper (C) reverses groups efficiently with O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Iterative helper method is standard optimal solution [OK]

Hint: Iterative helper reversal is optimal for O(1) space [OK]

Common Mistakes:

• Confusing recursion with iterative approach
• Assuming DP applies to linked list reversal
• Ignoring partial group handling

3. 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

4. Suppose the browser history must support reopening previously visited URLs multiple times without losing forward history (i.e., URLs can be revisited without clearing forward stack). Which modification to the two stacks approach correctly supports this feature?

hard

A. Use a doubly linked list with a current pointer, allowing moving back and forward without clearing forward history on visit.

B. Remove clearing of forward_stack in visit and allow duplicates in back_stack; back and forward remain unchanged.

C. Keep two stacks but add a third stack to track duplicates and manage forward history separately.

D. Use a single list with an index pointer and never slice the list on visit, allowing revisits without losing forward pages.

Solution

1. Step 1: Understand the requirement

   Revisiting URLs should not clear forward history, so forward pages must remain accessible after visit.

2. Step 2: Evaluate data structure modifications

   Two stacks approach relies on clearing forward_stack on visit, so it cannot support this without major changes. A doubly linked list with a current pointer allows moving back and forward freely without clearing forward history.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Doubly linked list supports revisits without losing forward history [OK]

Hint: Doubly linked list allows bidirectional navigation without clearing forward history [OK]

Common Mistakes:

• Removing forward_stack clearing breaks correctness in two stacks
• Adding extra stacks complicates without solving
• Single list without slicing causes stale forward pages

5. Suppose the linked list nodes can be reused multiple times (i.e., the list is circular or nodes can appear multiple times). Which modification to the odd-even rearrangement algorithm is necessary to handle this scenario correctly?

hard

A. Add a visited set to track nodes already processed to avoid infinite loops or duplicates

B. No modification needed; the original in-place algorithm works correctly even with reused nodes

C. Convert the list to an array first, then reorder and reconstruct the list to handle duplicates

D. Use recursion to process nodes and detect cycles automatically

Solution

1. Step 1: Identify problem with reused nodes

   If nodes are reused or list is circular, naive pointer traversal causes infinite loops or duplicates.

2. Step 2: Use a visited set

   Tracking visited nodes prevents revisiting and infinite loops, ensuring correct rearrangement.

3. Step 3: Why other options fail

   No modification ignores cycles; array conversion adds overhead; recursion risks stack overflow without cycle detection.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited set is standard for cycle detection in linked lists [OK]

Hint: Detect cycles with visited set to avoid infinite loops [OK]

Common Mistakes:

• Assuming original algorithm handles cycles or reused nodes
• Using recursion without cycle detection