Merge K Sorted Linked List in Kotlin

by

To merge K sorted linked lists, you can use the “merge K lists” algorithm, which is a variant of the merge sort algorithm. Here’s an algorithm to merge K sorted linked lists:

  1. If the number of lists K is 0, return null.
  2. If the number of lists K is 1, return the head of the only list.
  3. If the number of lists K is 2 or more, split the K lists into two groups of roughly equal size.
  4. Recursively merge the two groups of lists using the merge two lists algorithm (see below).
  5. Return the head of the merged list.

And here’s an algorithm to merge two sorted linked lists:

  1. Create a new dummy head node for the merged list.
  2. Initialize two pointers, curr and other, to point to the head of the two lists.
  3. Traverse the two lists using the following steps:
    • Compare the values at the curr and other nodes.
    • Append the node with the smaller value to the merged list, and move the corresponding pointer (curr or other) to the next node in its list.
    • Repeat this process until one of the pointers reaches the end of its list.
  4. Append the remaining nodes in the non-empty list to the end of the merged list.
  5. Return the head of the merged list (i.e., the next node after the dummy head node).

And here’s an implementation of the “merge K lists” algorithm in Kotlin:

Kotlin
class Node(var data: Int, var next: Node? = null)
fun mergeKLists(lists: Array<Node?>): Node? {
    if (lists.isEmpty()) {
        return null
    }
    
    if (lists.size == 1) {
        return lists[0]
    }
    
    val mid = lists.size / 2
    val left = lists.copyOfRange(0, mid)
    val right = lists.copyOfRange(mid, lists.size)
    
    val l1 = mergeKLists(left)
    val l2 = mergeKLists(right)
    
    return mergeTwoLists(l1, l2)
}

fun mergeTwoLists(l1: Node?, l2: Node?): Node? {
    val dummy = Node(0)
    var curr = dummy
    var p1 = l1
    var p2 = l2
    
    while (p1 != null && p2 != null) {
        if (p1.data < p2.data) {
            curr.next = p1
            p1 = p1.next
        } else {
            curr.next = p2
            p2 = p2.next
        }
        curr = curr.next!!
    }
    
    curr.next = p1 ?: p2
    return dummy.next
}
fun main() {
    // Create three sorted linked lists
    val l1 = Node(1, Node(4, Node(5)))
    val l2 = Node(1, Node(3, Node(4)))
    val l3 = Node(2, Node(6))
    
    // Merge the three lists into a single sorted list
    val mergedList = mergeKLists(arrayOf(l1, l2, l3))
    
    // Print the elements of the merged list
    var curr = mergedList
    while (curr != null) {
        print("${curr.data} ")
        curr = curr.next
    }
    // Output: 1 1 2 3 4 4 5 6
}

You can call the mergeKLists function with an array of Node objects representing your sorted linked lists, and it will return the head of the merged list.

main function in Kotlin that creates three linked lists, each of which is already sorted, and then merges them into a single sorted linked list using the mergeKLists function. we create three linked lists l1, l2, and l3, each of which is already sorted. We then call the mergeKLists function with an array containing these three lists, which merges them into a single sorted linked list. Finally, we traverse the merged list and print its elements to verify that it is indeed sorted.

Output : 1 1 2 3 4 4 5 6

Leave a Comment