Start learning free

LESSON 283 OF 348 · LINKED LISTS

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

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

    KOTLIN · LINKED LISTS

    Flatten Multilevel List in Kotlin, explained

    Problem overview

    Each Node has prev and next pointers and a child pointer, which may lead to another doubly linked list, which may have children of its own. The function flatten must merge all the levels into one doubly linked list, in place, and return the head. A child list goes right after its parent node, ahead of the parent's old successor.

    For levels 1-2-3-4-5-6, 7-8-9-10 under 3 and 11-12 under 8, the result is [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]. For 1-2 with child 3 under 1, it is [1, 3, 2]. An empty list stays empty.

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

    Approach: splice the child in, then keep walking

    A recursive solution flattens each child before splicing it. Here the order of work is reversed, and no recursion is needed. Walk the list with one pointer. When you reach a node with a child, splice the child list in as it is, even if it still has children of its own. Then keep walking. Because the child nodes are now part of the main list, the walker passes through them next, and when it reaches a child node that has its own child, it splices that one in too. Deeper levels are handled when their parent is reached.

    Splicing needs the last node of the child's own level, so a small helper, getTail, walks the child list along next until the end. That helper is not recursive and doesn't look at grandchildren. The walker itself covers every node once, and each getTail call covers the nodes of one level once, so the total is linear.

    Step by step

    1. Walk with a copy of head, in a var node. The parameter itself must stay unchanged because it is the return value.
    2. Loop while node is not null.
    3. Check for a child. Nodes without one just move the loop on.
    4. Save node.next in next, since the link is about to be overwritten.
    5. Find the child level's tail with getTail(node.child) and store it as childTail.
    6. Link node and its child in both directions: node.next = node.child, then the child's prev points at node. This comes before child is cleared.
    7. Clear node.child.
    8. Link childTail to the saved next, and, if next exists, link next.prev back to childTail.
    9. Move to node.next outside the if. After a splice this is the first child node, so the walk continues inside the spliced part and flattens nested levels without recursion.
    10. Return head. After the loop node is null, so it can't be the result.
    11. Write getTail(node): copy the node into a mutable variable and advance while it has a next. It stops on the last node, not on the null after it.

    The solution in Kotlin

    class Solution {
    fun getTail(node: Node?): Node? {
        var node = node
        while (node!!.next != null) {
            node = node.next
        }
        return node
    }
    fun flatten(head: Node?): Node? {
        var node = head
        while (node != null) {
            if (node.child != null) {
                val next = node.next
                val 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
    }
}

    The Kotlin details worth knowing:

    • Shadowing a parameter. var node = node in getTail declares a new local variable with the same name as the parameter. The parameter is read-only, but the copy can be reassigned. Kotlin warns that the name is shadowed.
    • node!!.next in the condition. The !! asserts that node isn't null and throws if it is. After it succeeds, Kotlin smart-casts the local variable to non-null for the body of the loop, so node.next needs no !!. This is safe because getTail is only called with a child that exists.
    • Property versus local. node.child is a mutable property, so Kotlin doesn't smart-cast it after node.child != null. That's why node.child!!.prev needs !!, while next, a local val, is smart-cast without it.
    • Returning head, not node. The local node is null at the end of the loop.

    Complexity

    Time: O(n). The main loop moves forward one node per iteration, and every node of the flattened list is visited once. getTail is called once per child list, and it walks only that list's own level, so each node is walked by getTail at most once: a node sits on exactly one level, and when it is reached as part of a child level it is walked once. Together that is at most about 2n steps.

    Space: O(1). Only a few pointers are used, with no recursion and no stack.

    Edge cases and common mistakes

    • Empty list. flatten(null) returns null. The loop never runs and getTail is never called.
    • Child on the last node. next is null, so the child's tail stays the end of the list and no prev is set.
    • Calling getTail on null. It would throw a NullPointerException, so only call it when child != null.
    • Returning node. It is null after the loop. Return head.
    • Clearing child too early. The next two lines read node.child, so clear it only after the links are made.
    • Skipping the back links. The list looks right going forward but is wrong going backward when prev is not updated at both ends of the splice.

    Testing

    • The three-level example flattens to [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6], and its prev links read the same order in reverse.
    • 1-2 with child 3 under 1 gives [1, 3, 2].
    • A list with no children is returned as it was.
    • 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