Start learning free

LESSON 306 OF 414 · LINKED LISTS

Flatten Multilevel List in Scala: Recursive In-Place 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 · d) time, where d is the maximum nesting depth of the child lists.


STEP 1 OF 13
    Ctrl + Enter to check

    SCALA · LINKED LISTS

    Flatten Multilevel List in Scala, explained

    Problem overview

    The method flatten receives the head of a doubly linked list whose nodes (Node) have three links: prev, next and child. A child may point to the head of a separate doubly linked list, and the nodes of that list can have children of their own, so the structure has several levels. The method must flatten it into one level, in place, and return the head.

    In the first example, the top level is 1-2-3-4-5-6, node 3 has a child list 7-8-9-10, and node 8 has a child list 11-12. The flattened list is [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]. Each child list is inserted right after its parent, before the parent's old next. In the second example, 1-2 with a child 3 under node 1 becomes [1, 3, 2]. An empty list stays empty.

    Approach: flatten the deepest levels first

    Walk along one level. When a node has a child, three things must happen: the child list becomes the node's next, the end of the child list is joined to the node's old next, and the node's child is cleared.

    The child list may itself contain nodes with children. The simplest way to handle that is to flatten the child list first, with the same method, and then splice the result in. A recursive helper, flattenLevel, does this. It flattens the level that starts at the node it receives and returns the tail of the flattened result, the last node. The caller needs that tail to reconnect the rest of the parent level.

    Because every splice happens in place, the first node of the list never changes, so flatten returns the same head it was given.

    Step by step

    1. Delegate to a helper. flatten calls flattenLevel(head), ignores the returned tail, and ends with head.
    2. Declare the helper before flatten. It takes a Node named node, the first node of a level, and returns a Node, the tail of the flattened level.
    3. Copy the parameter into variables. Parameters can't be reassigned, so var cur walks the level and var tail remembers the last node visited. Both start at node. For an empty list, the loop never runs and the helper returns null.
    4. Loop while cur != null, so every node on this level is visited.
    5. Check for a child with cur.child != null. Nodes without one need nothing.
    6. Save cur.next in val next. Once cur.next points to the child, the old successor would otherwise be lost.
    7. Flatten the child list recursively and keep the tail it returns in val childTail. The recursive call handles all deeper levels.
    8. Link cur to its child in both directions: cur.next = cur.child, then cur.child.prev = cur. Both lines read cur.child, so they must run before it is cleared.
    9. Clear the child pointer: cur.child = null. A flattened list has no child links left.
    10. Reconnect the saved rest of the level. Set childTail.next = next, and only when next is not null, set next.prev = childTail.
    11. Record and advance. After the if, set tail = cur and cur = cur.next. After a splice, cur.next is the child, so the loop walks through the spliced nodes too, and tail ends up on the true last node.
    12. Return tail after the loop. This is what the recursive call stores in childTail.

    The solution in Scala

    class Solution {
    def flattenLevel(node: Node): Node = {
        var cur = node
        var tail = node
        while (cur != null) {
            if (cur.child != null) {
                val next = cur.next
                val childTail = flattenLevel(cur.child)
                cur.next = cur.child
                cur.child.prev = cur
                cur.child = null
                childTail.next = next
                if (next != null) {
                    next.prev = childTail
                }
            }
            tail = cur
            cur = cur.next
        }
        tail
    }

    def flatten(head: Node): Node = {
        flattenLevel(head)
        head
    }
}

    The Scala details worth knowing:

    • var and val. cur and tail change as the loop runs, so they are var. next and childTail are assigned once per splice, so they are val, and each loop iteration that splices gets fresh ones.
    • A recursive method needs a result type. Scala requires the return type to be written on a recursive method, which is why the signature says : Node. The compiler can't infer it from a body that calls itself.
    • The last expression is the value. The helper ends with tail and flatten ends with head, with no return. The call flattenLevel(head) on its own line is an expression whose value is simply discarded.
    • Assigning through a chain. cur.child.prev = cur reads the field child and then assigns to prev on that node. The assignment is allowed because prev is a var field of Node.
    • The null check on next. null is a valid value for Node, and writing next.prev when next is null would throw a NullPointerException.

    Complexity

    Time: O(n), where n is the total number of nodes. Every node is visited by exactly one loop: the loop of the level where it started, or, after a splice, the loop of the level it was spliced into. Splicing is constant work per child.

    Space: O(d), where d is the deepest nesting of child lists, for the recursion stack. The list itself is rewired in place and no nodes are created. A very deep chain of children could in principle overflow the stack.

    Edge cases and common mistakes

    • Empty list. head = null makes the loop skip at once, and flatten returns null.
    • A child on the last node. Then next is null. The child list just becomes the end of the list, and the guard prevents a null dereference.
    • Forgetting to clear child. The result looks right when printed through next links, but nodes still carry child pointers, so the list is not truly single-level.
    • Losing the rest of the level. Overwriting cur.next before saving it cuts off nodes 4, 5 and 6 in the first example.
    • Not setting both directions. Updating only next and leaving prev stale gives a list that can be walked forward but is broken when walked backward.
    • Using the wrong tail. Reconnecting the old next to the child's head, instead of to the end of the flattened child list, would drop everything after the first node of the child.
    • Returning cur. After the loop it is null. The helper returns tail, and flatten returns head.

    Testing

    • The first example, 1-2-3-4-5-6 with children under 3 (7-8-9-10) and under 8 (11-12), gives [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6].
    • 1-2 with a child 3 under node 1 gives [1, 3, 2].
    • An empty list gives an empty list.
    • 1-2-3 with a child 4 under node 1 and a child 5 under node 2 gives [1, 4, 2, 5, 3].
    • Walking the flattened first example backward through prev from its last node gives [6, 5, 4, 10, 9, 12, 11, 8, 7, 3, 2, 1].
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free