Start learning free

LESSON 282 OF 348 · LINKED LISTS

Flatten a Multilevel Doubly Linked List in Kotlin: Recursive O(n)

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

    KOTLIN · LINKED LISTS

    Flatten Multilevel List in Kotlin, explained

    Problem overview

    Each Node in this doubly linked list has prev and next pointers and a third pointer, child, which may point to the head of another doubly linked list. Those child lists can have children of their own. The function flatten must turn the whole structure into a single-level doubly linked list, in place, and return the head.

    The order is depth first: when a node has a child list, that whole list (with everything below it) goes right after the node, before the node's old next. For the example with levels 1-2-3-4-5-6, 7-8-9-10 hanging below 3 and 11-12 hanging below 8, the result is [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]. For 1-2 with a child 3 under 1, it is [1, 3, 2]. An empty list stays empty.

    This lesson's version must be recursive and run in O(n) time.

    Approach: flatten each child first, then splice it in

    Think about one level. Walk along it, and whenever a node has a child, the child list must be spliced between that node and its old successor. The child list may itself contain children, so the splice is only correct after the child list is fully flat. That is a recursive structure: flattening a level means flattening each child level first.

    The splice needs the last node of the flattened child list, because that node must connect forward to the old next. So the recursive helper returns the tail of the level it flattened. Each pointer is rewired once, and for a list that isn't nested very deeply the work is proportional to the number of nodes.

    Step by step

    1. Write flatten around a helper. flatten calls flattenLevel(head) and returns head. Everything happens in place, so the first node never changes.
    2. Define flattenLevel(node) taking the first node of a level, and returning the tail of the flattened level. Parameters are read-only in Kotlin, so copy node into var cur (the walker) and var tail (the last node visited). For a null level the loop never runs and null is returned.
    3. Loop while cur is not null.
    4. Check for a child. Only nodes with a child need rewiring.
    5. Save cur.next in next before changing it. Once cur.next points at the child, the rest of the level could not be reached any more.
    6. Flatten the child level recursively and keep the tail it returns as childTail.
    7. Link cur to its child in both directions: cur.next = cur.child, and the child's prev points back at cur. Both lines read cur.child, so they come before it is cleared.
    8. Clear cur.child. A flat list has no child pointers.
    9. Link childTail to the saved next: set childTail.next, and, if next exists, set next.prev back to childTail.
    10. Advance. After the if, record tail = cur and move to cur.next. After a splice, cur.next is the child, so the loop also walks the spliced nodes, and tail ends on the real last node.
    11. Return tail after the loop.

    The solution in Kotlin

    class Solution {
    fun 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
        }
        return tail
    }
    fun flatten(head: Node?): Node? {
        flattenLevel(head)
        return head
    }
}

    The Kotlin details worth knowing:

    • Smart cast on locals only. Inside while (cur != null), the local var cur is known to be non-null, so cur.child and cur.next need no ?.. But cur.child is a mutable property, and another piece of code could change it between the check and the use, so Kotlin doesn't smart-cast it. That's why cur.child!!.prev needs !!.
    • childTail!!. The helper's return type is Node?, but for a non-empty child list the tail is never null, so !! is safe.
    • A local val smart-casts. The check if (next != null) lets next.prev compile without !!, because next is a local val that can't change after the check.
    • The return value of flattenLevel is ignored by flatten. Only the recursive call inside the helper uses it. Kotlin allows discarding a returned value.

    Complexity

    Time: about O(n) for shallow nesting. Each splice is a constant number of pointer changes, and each node's own level loop visits it once. But the spliced nodes are walked again by the loop of the level above, and again by the level above that. A node nested d levels deep is therefore visited up to d + 1 times, so the worst case is O(n * d), which grows to O(n²) when each level holds one node and the nesting is as deep as the list is long. For ordinary inputs, with few levels, it behaves like O(n).

    Space: O(d), where d is the nesting depth, for the recursion stack. A very deep structure can overflow the stack.

    Edge cases and common mistakes

    • Empty list. With head = null the loop doesn't run, and flatten returns null.
    • Child on the last node. Then next is null. The child's tail ends the list, and there's no prev to set.
    • Forgetting to clear child. The list would be linked correctly but still show child pointers.
    • Losing the old next. If you overwrite cur.next before saving it, the remainder of the level is lost.
    • Setting only next links. The result must also be correct backwards. Missing prev updates give a list that looks right going forward but is broken in reverse.
    • Returning the wrong thing. flatten returns the original head. The tail is only for the recursion.

    Testing

    • The three-level example flattens to [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6], and walking back from the last node through prev gives 6, 5, 4, 10, 9, 12, 11, 8, 7, 3, 2, 1.
    • 1-2 with child 3 under 1 gives [1, 3, 2].
    • A list with no children is returned unchanged.
    • null gives null.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free