Flatten a multilevel linked list

Flatten a list whose nodes can each hang a child list off of them, splicing every child in depth-first so the result is one plain list.

The idea

Walk the main list node by node. A node with a child is hiding a whole extra list underneath it: splice that child in right after the node, reconnect the child's tail to whatever used to come next, and clear the child pointer so the structure is a single flat list again.

Code

public static Node Flatten(Node head) {
    for (Node n = head; n != null; n = n.next) {
        if (n.child == null) continue;
        Node childTail = n.child;
        while (childTail.next != null) childTail = childTail.next;
        childTail.next = n.next;
        n.next = n.child;
        n.child = null;
    }
    return head;
}

Tips

• A real multilevel list can nest several levels deep — handle that by recursing (or using an explicit stack) each time a splice reveals another child.
• Clearing child to null afterwards matters: a flattened list should not still claim to have nested children.

In the .NET library

This demo flattens one child list for clarity; the general solution recurses (or keeps an explicit stack of 'what comes next' addresses) so a child's own child gets flattened too, depth first.