Start learning free

LESSON 282 OF 347 · LINKED LISTS

Flatten Multilevel List in C#: Iterative O(n) Splicing

Practice O(n) 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 iterative (non-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 has prev and next pointers and a child pointer that may lead to another doubly linked list, which can have children of its own. Flatten(head) must rewire the nodes into one single-level doubly linked list and return the head. This version must not use recursion and must run in O(n) time.

    A child list goes right after its parent node and before the parent's old next. For the first example, the top level 1 to 6 has a child list 7, 8, 9, 10 under node 3, 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]. The second example, 1---2 with child 3 under node 1, becomes [1, 3, 2], and an empty list stays empty.

    Approach: splice as you walk

    A recursive solution flattens each child before splicing it in. The iterative idea gets the same result with a single loop and a trick: splice the child list in without flattening it first, and keep walking.

    When the walker reaches a node with a child, it moves the child list in right after the node. The walker then steps onto the first child node, and from there continues through the child list as if it had always been part of the level. If one of those nodes has a child of its own, the walker meets it later and splices that list in at that point. By the time the walker reaches the end, every child has been spliced in, at every depth, in the right order. A nested list is never lost, because its parent is always visited before the nodes that follow it.

    To splice a child list in, you need its last node, so the old next can be attached after it. A small helper, GetTail, finds it by walking the child's own level. That walk only covers the child's own siblings. Deeper lists are handled later, when the main loop reaches their parents.

    Step by step

    1. Start a walker. node begins at head. The head itself must not move, because it is the value you return.
    2. Loop while node != null, so every node on the level, and later every spliced node, is visited.
    3. Check for a child. Nodes without one just let the loop move on.
    4. Save node.next in next. Pointing node.next at the child in a moment would otherwise make the rest of the level unreachable.
    5. Find the child list's tail with GetTail(node.child) and keep it as childTail. It only walks the child's own level.
    6. Link the node and its child both ways: node.next is the child and the child's prev is the node. Both lines read node.child, so they come before it is cleared.
    7. Clear node.child, because a flattened list has no child pointers.
    8. Reconnect the saved part. childTail.next becomes next, and if next is not null, its prev points back to childTail.
    9. Advance node to node.next. After a splice this is the first child node, so the loop walks through the spliced nodes and flattens deeper levels along the way.
    10. Return head after the loop. Returning node would be wrong, because by then it is null.
    11. Write GetTail above Flatten, taking and returning a Node.
    12. Walk to the last node. Keep moving while node.next != null, then return node. The loop must stop on the last real node, not on the null after it.

    The solution in C#

    class Solution {

    public Node GetTail(Node node) {
        while (node.next != null) {
            node = node.next;
        }
        return node;
    }

    public Node Flatten(Node head) {
        Node node = head;
        while (node != null) {
            if (node.child != null) {
                Node next = node.next;
                Node childTail = GetTail(node.child);
                node.next = node.child;
                node.child.prev = node;
                node.child = null;
                childTail.next = next;
                if (next != null) {
                    next.prev = childTail;
                }
            }
            node = node.next;
        }
        return head;
    }
};

    Some details worth a closer look:

    • References, not copies. Node is a class, so Node next = node.next stores a reference to the same node. It keeps pointing at the old successor after node.next is reassigned.
    • Moving node doesn't move head. Both are separate variables that happen to start with the same reference. That is why head is still the first node when the loop ends.
    • GetTail assumes a non-null argument. It reads node.next immediately, which is safe because it's only called when node.child != null.
    • The trailing semicolon after the class. C# permits a ; after a class declaration, so }; compiles. It does nothing.

    Tracing the first example

    The walker visits 1 and 2, which have no children. At node 3 the child list 7, 8, 9, 10 is spliced in: the tail is 10, and 10 is attached to the old next, node 4. The list is now 1, 2, 3, 7, 8, 9, 10, 4, 5, 6, with node 8 still holding its child. The walker moves to 7, then reaches 8. Its child list 11, 12 is spliced between 8 and 9, giving 1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6. The walker carries on through 11, 12, 9, 10, 4, 5 and 6 and stops. That is the expected order.

    Complexity

    Time: O(n). The main loop visits every node once, because a spliced node is only reached after it has been spliced in. GetTail walks each child list's own level exactly once, since that level is still untouched when its parent is reached. Together that is about two visits per node, and the splice itself is a fixed number of pointer changes.

    Space: O(1). The code uses a few local references and no recursion or other data structures. That is the advantage over the recursive version, whose stack grows with the nesting depth.

    Edge cases and common mistakes

    • Empty list. With head == null the loop is skipped and null is returned.
    • A child on the last node of a level. Then next is null, so the back link has to be guarded. Without the check, next.prev = childTail throws a NullReferenceException.
    • Children inside children. They need no special code. The walker steps into the spliced list and finds them there.
    • Not clearing child. The result would still contain child pointers.
    • Clearing child too early. node.child = null before node.child.prev = node throws a NullReferenceException.
    • Forgetting the prev links. The list would look correct going forward and be wrong going backward.
    • Stopping GetTail one step too late. A loop on node != null ends with node equal to null, and the next line would throw.

    Testing

    • The three-level example 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 list with no children comes back unchanged.
    • An empty list gives null.

    To check the prev links, walk backward from the last node. For the first example, the order should be 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