Bloomberg Interview Question: Flatten a Multi-level Linked List

Problem

You have a linked list where each node has:

• next: the next node on the same level
• down: an optional pointer to a child list

Flatten it into a single list by splicing each down chain between the node and its original next, preserving order.

Conceptual example

Top level:

[1] -> [2] -> [3] -> [8] -> [10]
              |
              v
             [4] -> [5] -> [6]
                          |
                          v
                         [7]

[8] also has a down chain:
[8]
 |
 v
[9]

Flattened:

[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10]

Approach

Two common solutions:

• Recursion: flatten the down list, connect it after current node, then reconnect the saved next.
• Stack: when seeing a down, push next to stack, go down first; when reaching end, pop and continue.

Python (recursive)

class Node:
    def __init__(self, val, next=None, down=None):
        self.val = val
        self.next = next
        self.down = down


def flatten(head: Node) -> Node:
    if not head:
        return None

    curr = head
    while curr:
        if curr.down:
            next_node = curr.next
            down_head = flatten(curr.down)
            curr.next = down_head
            curr.down = None

            tail = down_head
            while tail and tail.next:
                tail = tail.next
            if tail:
                tail.next = next_node
        curr = curr.next

    return head

Python (stack)

def flatten_iterative(head: Node) -> Node:
    if not head:
        return None

    stack = []
    curr = head

    while curr:
        if curr.down:
            if curr.next:
                stack.append(curr.next)
            curr.next = curr.down
            curr.down = None

        if not curr.next and stack:
            curr.next = stack.pop()

        curr = curr.next

    return head

Complexity

• Time: O(n)
• Space: O(d) recursion depth or stack depth

Need interview help? Contact OA VO Service

• 📧 Email: [email protected]
• 📱 Phone: +86 17863968105

Need real interview questions? Contact WeChat: Coding0201 to get the questions.