Bird
Raised Fist0
Interview Prepcustom-data-structuresmediumAmazonMicrosoftGoogle

Flatten a Multilevel Doubly Linked List

Choose your preparation mode4 modes available
📋
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
}
0/9
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
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}

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.

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}

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

t2_01edge
Input{"head":null}
Expectednull

Empty list input should return null.

t2_02edge
Input{"head":[1]}
Expected{"val":1,"prev":null,"next":null,"child":null}

Single node with no child remains unchanged after flattening.

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}

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

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}

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.

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}

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

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}

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

t4_01performance
Input{"head":[1]}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
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. 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. Consider the following buggy code for partitioning a linked list around value x. Which line contains the subtle bug that can cause an infinite loop or incorrect list structure?
medium
A. Line where less_tail is updated to current
B. Line where current.next is set to less_tail.next
C. Missing line to set the last node's next to None
D. Line where prev.next is updated to current.next

Solution

  1. Step 1: Identify the bug from known mistakes

    The code does not explicitly terminate the greater or equal partition's last node with None, which can cause cycles or incorrect traversal.
  2. Step 2: Confirm no line sets last node's next to None

    All pointer updates are correct, but missing termination leads to infinite loops or corrupted list.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Proper termination of the list is essential to avoid cycles [OK]
Hint: Always terminate the last node's next with None [OK]
Common Mistakes:
  • Forgetting to set last node's next to None
  • Incorrect pointer updates causing lost nodes
  • Misplacing less_tail pointer updates
4. What is the space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?
medium
A. O(n) -- recursion stack uses space proportional to list length
B. O(1) -- only constant extra pointers used
C. O(log n) -- recursion depth is halved each call
D. O(n^2) -- due to repeated pointer updates in recursion

Solution

  1. Step 1: Identify recursion depth

    The helper function recurses once per node, so recursion depth is n.
  2. Step 2: Calculate space usage

    Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Recursion stack proportional to list length [OK]
Hint: Recursion depth equals list length -> O(n) space [OK]
Common Mistakes:
  • Assuming constant space due to in-place changes
  • Confusing recursion depth with log n
  • Overestimating to quadratic space
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard