Sort the Linked List of 0’s 1’s and 2’s in Kotlin

by

To sort a linked list containing only 0’s, 1’s, and 2’s, you can use the Dutch national flag algorithm, which is an efficient algorithm that sorts an array containing three distinct values in linear time. Here are the steps to implement this algorithm for a linked list:

  1. Traverse the linked list and count the number of 0’s, 1’s, and 2’s.
  2. Traverse the list again and overwrite each node with a 0 until you have written the correct number of 0’s.
  3. Write the correct number of 1’s after the 0’s.
  4. Write the correct number of 2’s after the 1’s.
Kotlin
class Node(var data: Int, var next: Node?)

fun sortLinkedList(head: Node?): Node? {
    // Count the number of 0's, 1's, and 2's in the list
    var count0 = 0
    var count1 = 0
    var count2 = 0
    var curr = head
    while (curr != null) {
        when (curr.data) {
            0 -> count0++
            1 -> count1++
            2 -> count2++
        }
        curr = curr.next
    }

    // Rebuild the list with the sorted nodes
    curr = head
    var i = 0
    while (curr != null) {
        if (i < count0) {
            curr.data = 0
        } else if (i < count0 + count1) {
            curr.data = 1
        } else {
            curr.data = 2
        }
        i++
        curr = curr.next
    }

    return head
}

fun main() {
    // Create an unsorted linked list containing 0's, 1's, and 2's
    val head = Node(1, Node(0, Node(2, Node(1, Node(2, null)))))

    // Sort the linked list
    val sortedHead = sortLinkedList(head)

    // Print the sorted linked list
    var curr = sortedHead
    while (curr != null) {
        print("${curr.data} ")
        curr = curr.next
    }
    // Output: 0 1 1 2 2
}

this implementation, we first traverse the list and count the number of 0’s, 1’s, and 2’s. We then traverse the list again and overwrite each node with the correct value in the correct order. The repeat function is used to write the correct number of each value. Finally, we return the head of the sorted list.

main function in Kotlin that creates a linked list of 0’s, 1’s, and 2’s, sorts it using the sortLinkedList function, and prints the sorted list: 0 1 1 2 2

Leave a Comment