Start learning free

LESSON 281 OF 347 · LINKED LISTS

Flatten Multilevel List in C#: Recursive Splicing

Practice O(n) Recursive Read the full explanation

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not 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, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

 

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:



After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:

The input multilevel linked list is as follows:

  1---2---NULL
  |
  3---NULL

Example 3:

Input: head = []
Output: []

 

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

 


Note:

Your algorithm should be recursive and run in O(n) time.


STEP 1 OF 12
    Ctrl + Enter to check

    C# · LINKED LISTS

    Flatten Multilevel List in C#, explained

    Problem overview

    Each Node in this doubly linked list has prev and next pointers, plus a child pointer that may lead to a separate doubly linked list. Those child lists can have children of their own, to any depth. Flatten(head) must turn the whole structure into one single-level doubly linked list and return its head.

    The order is depth first: when a node has a child list, that whole list (with its own descendants) goes right after the node, before the node's old next. For the first example, the top level is 1 to 6, node 3 has a child list 7, 8, 9, 10, and node 8 has a child list 11, 12. The flattened order is [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]. In the second example, 1---2 with a child list 3 under node 1 becomes [1, 3, 2]. An empty list stays empty.

    The note asks for a recursive algorithm that runs in O(n) time.

    Approach: flatten the child first, then splice it in

    Walk along one level. Most nodes have no child and need nothing. When a node does have one, three things must happen:

    1. Flatten the child list. This is the recursive part: a child list is the same problem as the original, just smaller.
    2. Insert the flattened child list between the node and the node's old next.
    3. Clear the node's child pointer.

    To reconnect the old next after the child list, you need the last node of the flattened child list, its tail. So the helper does double duty: it flattens a list in place and returns the tail of the result. The caller uses that tail to attach the rest of its own level.

    There is one subtle point about the walk. After a splice, the node's next is the child, so the loop continues through the spliced nodes and then on to the old next. That walk is harmless, because the spliced nodes have no children left, but it means the loop's last visited node is the true tail of the whole flattened level, nested nodes included.

    Step by step

    1. Write Flatten in terms of a helper. FlattenLevel(node) flattens the list starting at node in place and returns the tail. Flatten calls it and returns head. The pointers are rewired but no node is replaced, so the head never changes.
    2. Declare the helper with a Node parameter and a Node return type.
    3. Track the tail. A variable tail starts at node. For an empty list, the loop never runs and the helper returns null, which is the correct tail of nothing.
    4. Loop over the level while node != null.
    5. Look for a child. Only nodes with a child need work.
    6. Save node.next in next. The next step overwrites that pointer, and without the saved copy the rest of the level would be unreachable.
    7. Recurse into the child and store the returned tail as childTail.
    8. Link the node and its child in both directions: node.next points to the child and the child's prev points back. Do this before clearing the child pointer, because both lines read it.
    9. Clear node.child. A flattened list must not keep child pointers.
    10. Reconnect the saved part of the level. childTail.next becomes next. If next exists, its prev must point back at childTail. If the node was the last in its level, next is null and there is no back pointer to set.
    11. Advance. After the if, remember the current node as tail, then move node forward.
    12. Return tail, the last node visited.

    The solution in C#

    class Solution {

    public Node FlattenLevel(Node node) {
        Node tail = node;
        while (node != null) {
            if (node.child != null) {
                Node next = node.next;
                Node childTail = FlattenLevel(node.child);
                node.next = node.child;
                node.child.prev = node;
                node.child = null;
                childTail.next = next;
                if (next != null) {
                    next.prev = childTail;
                }
            }
            tail = node;
            node = node.next;
        }
        return tail;
    }

    public Node Flatten(Node head) {
        FlattenLevel(head);
        return head;
    }
}

    Some details worth a closer look:

    • Nodes are references. Node is a class, so Node next = node.next copies a reference, not a node. The saved next still points at the original node after node.next is reassigned.
    • The helper's result is ignored in Flatten. C# allows calling a method that returns a value and discarding it. Only the recursive call inside the helper needs the tail.
    • The parameter node is a local variable. Moving it forward inside the loop doesn't change the caller's variable. Assigning to a parameter only changes the method's own copy of the reference.
    • Null checks are explicit. node.child != null is how C# asks whether a child exists.

    Tracing the second example

    Start with 1---2 and node 1 having the child 3. At node 1, the saved next is node 2. The recursive call on node 3 finds no child and returns 3 as the tail. Then node 1's next becomes node 3, node 3's prev becomes node 1, and node 1's child is cleared. The tail's next becomes node 2, and node 2's prev becomes node 3. The loop continues from node 1 to 3 to 2, and the result is 1---3---2.

    Complexity

    Time. Splicing one child list in is a fixed number of pointer changes, and every node is visited by the loop of its own level. The catch is the walk after a splice: the loop of each ancestor level also walks over the nodes spliced in below it. A node at nesting depth d is therefore visited up to d + 1 times, so the running time is O(n · d). When the nesting is shallow, that is close to O(n), which is the target in the problem's note. In the worst case, a single chain where every node's child holds the next node, d is about n and the work is quadratic. Running this code on such a chain of 100, 200 and 400 nodes makes 5,050, 20,100 and 80,200 loop visits.

    The iterative version in the second lesson walks each level once to find its tail and once in its main loop, which keeps the work at O(n) for every shape.

    Space: O(d) for the recursion stack, where d is how deep the children nest. In the worst case, a chain of children inside children, that is O(n). No extra data structures are used.

    Edge cases and common mistakes

    • Empty list. Flatten(null) returns null because the loop is skipped.
    • Child on the last node of a level. Here next is null. Writing next.prev = childTail without the check throws a NullReferenceException.
    • Forgetting to clear child. The flattened list would still have child pointers, so it would not be a proper single-level list.
    • Losing the old next. If node.next is overwritten before it is saved, the rest of the level disappears.
    • Skipping the prev pointers. A list with correct next links but wrong prev links looks right going forward and breaks going backward.
    • Clearing the child too early. Setting node.child = null before node.child.prev = node throws a NullReferenceException.
    • Returning something other than the tail from the helper. The caller needs the last node to reconnect its level.

    Testing

    • The three-level example from the problem gives [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6].
    • 1---2 with child 3 under node 1 gives [1, 3, 2].
    • A single node with no child stays [1].
    • An empty list returns null.

    Also walk backward from the last node using prev. For the first example you should see 6, 5, 4, 10, 9, 12, 11, 8, 7, 3, 2, 1.

    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free