Flattening a Linked List in Kotlin

“Flattening” a linked list refers to the process of converting a nested linked list into a single-level linked list.

A nested linked list is a linked list where the nodes can contain references to other linked lists. For example, consider the following nested linked list:

1 -> 2 -> 3 -> 4 -> 5
|
v
6 -> 7 -> 8
|
v
9 -> 10

In this example, the nodes with values 3 and 6 contain references to other linked lists.

To flatten this linked list, we need to convert it into a single-level linked list where each node contains only a single value and a reference to the next node.

The flattened version of the above linked list would look like this: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

In this flattened linked list, each node contains only a single value and a reference to the next node.

Flattening a linked list can be a useful operation for certain types of algorithms and data structures.

class ListNode(var `val`: Int) {
    var next: ListNode? = null
    var child: ListNode? = null
    var prev: ListNode? = null
}
fun flatten(head: ListNode?): ListNode? {
    if (head == null) {
        return null
    }
    var curr: ListNode? = head
    var prev: ListNode? = null
    while (curr != null) {
        if (curr.child != null) {
            val childHead = curr.child
            val childTail = getTail(childHead!!)
            if (prev != null) {
                prev.next = childHead
            } else {
                head.next = childHead
            }
            childHead.prev = prev
            childTail.next = curr.next
            if (curr.next != null) {
                curr.next!!.prev = childTail
            }
            curr.child = null
            curr = childTail
        } else {
            prev = curr
            curr = curr.next
        }
    }
    return head
}

fun getTail(head: ListNode): ListNode {
    var curr = head
    while (curr.next != null) {
        curr = curr.next!!
    }
    return curr
}

fun main() {
    // Create a linked list with nested child lists
    val head = ListNode(1)
    val node2 = ListNode(2)
    val node3 = ListNode(3)
    val node4 = ListNode(4)
    val node5 = ListNode(5)
    val node6 = ListNode(6)
    val node7 = ListNode(7)
    val node8 = ListNode(8)
    val node9 = ListNode(9)
    val node10 = ListNode(10)
    head.next = node2
    node2.prev = head
    node2.next = node3
    node3.prev = node2
    node3.next = node4
    node4.prev = node3
    node4.next = node5
    node5.prev = node4
    node5.next = node6
    node6.prev = node5
    node3.child = node7
    node7.next = node8
    node8.prev = node7
    node8.next = node9
    node9.prev = node8
    node9.next = node10
    node10.prev = node9

    // Flatten the linked list
    val flattenedHead = flatten(head)

    // Print the flattened linked list
    var curr: ListNode? = flattenedHead
    while (curr != null) {
        println(curr.`val`)
        curr = curr.next
    }
}

In this implementation, we define a ListNode class that represents a node in the linked list. Each node contains an integer value (val), a reference to the next node (next), and a reference to a child node (child) that can itself be a nested linked list.

The flatten function takes a head parameter that points to the head of a nested linked list. The function uses a modified depth-first search algorithm to traverse the linked list, flattening each child node recursively until it reaches a leaf node.

The algorithm works as follows:

1. If the head parameter is null, return null immediately.
2. Initialize a curr variable to point to the head node.
3. While curr is not null: a. If curr has a child node, recursively flatten the child node by calling flatten(curr.child) and assign the result to a new child variable. b. If curr has a child node, rewire the next and child pointers: – Set curr.next to child. – Set child.prev to curr. – Set curr.child to null. – Traverse curr to the end of the new list by repeatedly following the next pointer. – Set curr.next to the original next node (if it exists). – If curr.next is not null, set curr.next.prev to curr. c. Traverse to the next node in the original list by following the next pointer of curr.
4. Return the head node of the flattened list.

main function creates a linked list with nested child lists, as shown below:

1 -> 2 -> 3 -> 4 -> 5 -> 6
|
7 -> 8 -> 9 -> 10

It then calls the flatten function to flatten the linked list, and prints the flattened linked list in the while loop. The expected output should be:

1
2
7
8
9
10
3
4
5
6