The O(n) Club: Flatten a Multilevel Doubly Linked List — Now with 100% Less NullPointerException

The O(n) Club: Flatten a Multilevel Doubly Linked List — Now with 100% Less NullPointerException

⚡ TL;DR

Take your multi-level doubly linked list (aka the Matryoshka doll of headaches) and flatten all those sneaky child lists right after their parents. Recursion is your best friend here, and pointer mistakes are your worst enemy.

For the love of null safety, update next, prev, and nuke those child pointers when you’re done. Please don’t brute-force this—unless you enjoy LinkedIn recruiters messaging you about “unique opportunities” for code refactoring.

Here’s the “don’t even think about it” brute-force example:

// Do NOT try this at home.
public Node flatten(Node head) {
    // Collect all nodes via traversal, then reconnect.
    // Good luck handling prev/next/child mess...
    return head == null ? null : actuallyDoItBetter(head);
}

🧠 How Devs Usually Mess This Up

Late-night coding? Watch for these:

🔍 What’s Actually Going On

Picture your linked list as a retro file explorer, and child is like those weird hidden folders-within-folders your boss expects you to document. Flattening means: dive into every sublist, flatten it right after its parent, and tie everyone together so both next and prev work perfectly—because even data structures need healthy family connections.

Key rules:

🛠️ PseudoCode

• Start at the head: curr = head
• While curr exists:
  • If curr.child == null: Move along to curr.next
  • If curr.child != null:
    • Stash curr.next as next
    • Flatten curr.child (recursively!)
    • Insert flattened child list after curr
    • Connect prev/next at the seams so nobody gets lost
    • Walk to the child tail, reattach next, update next.prev if needed
    • Set curr.child = null
  • Advance: curr = curr.next

// Java-style pseudo:
Node flatten(Node head):
    curr = head
    while curr != null:
        if (curr.child != null):
            next = curr.next
            child = flatten(curr.child)
            curr.next = child
            child.prev = curr
            tail = child
            while tail.next != null:
                tail = tail.next
            tail.next = next
            if (next != null):
                next.prev = tail
            curr.child = null
        curr = curr.next
    return head

💻 The Code

// Node definition
class Node {
    public int val;
    public Node prev, next, child;
    public Node(int val) { this.val = val; }
}
 public Node flatten(Node head) {
    if (head == null) return null;
    flattenDFS(head);
    return head;
}
 private Node flattenDFS(Node node) {
    Node curr = node;
    Node last = null;
    while (curr != null) {
        Node next = curr.next;
        if (curr.child != null) {
            Node childTail = flattenDFS(curr.child);
            curr.next = curr.child;
            curr.child.prev = curr;
             if (next != null) {
                childTail.next = next;
                next.prev = childTail;
            }
            curr.child = null;
            last = childTail;
        } else {
            last = curr;
        }
        curr = next;
    }
    return last;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t assume only one level: child lists can have children and so on. Nesting is infinite, just like your to-do list.
• Missing prev pointer updates will make traversal painful. Both ways.
• Leaving child pointers non-null makes for ghost bugs in UI displays and APIs.
• Time: O(n) for n nodes. Space: O(depth) for recursion stack—just like your anxiety.

🧠 Interviewer Brain-Tattoo

If you only flatten the top, don’t be shocked when bugs crawl up from the data dungeon. Flatten deep for peace of mind.