merge-two-sorted-lists.kt

fun mergeTwoSortedLists(L1: ListNode<Int>, L2: ListNode<Int>): ListNode<Int> {
    println("merging $L1 and $L2")
    val dummyHead = ListNode(Random.nextInt(), null)
    var current = dummyHead
    var p1 = L1
    var p2 = L2
    while (p1.next != null && p2.next != null) {
        if (p1.data <= p2.data) {
            current.next = p1
            p1 = p1.next!!
        } else {
            current.next = p2
            p2 = p2.next!!
        }
        // move pointer forward
        current = current.next!!
    }
    // end of L1 or L2

    // deal with the longer list
    var isL2AllProcessed = false
    if (p2.next == null) {
        while (p1.next != null) {
            if (isL2AllProcessed || (!isL2AllProcessed && p1.data <= p2.data)) {
                current.next = p1
                p1 = p1.next!!
            } else {
                current.next = ListNode(p2.data, null)
                isL2AllProcessed = true
            }
            current = current.next!!
        }
        if (isL2AllProcessed) {
            current.next = p1
        }
    }

    var isL1AllProcessed = false
    if (p1.next == null) {
        while (p2.next != null) {
            if (isL1AllProcessed || (!isL1AllProcessed && p2.data <= p1.data)) {
                current.next = p2
                p2 = p2.next!!
            } else {
                val new = ListNode(p1.data, null)
                current.next = new
                isL1AllProcessed = true
            }
            current = current.next!!
        }
        if (isL1AllProcessed) {
            current.next = p2
        }
    }

    // end of both list
    if (!isL1AllProcessed && !isL2AllProcessed) {
        if (p1.data <= p2.data) {
            val new = ListNode(p1.data, null)
            current.next = new
            new.next = p2
        } else {
            val new = ListNode(p2.data, null)
            current.next = new
            new.next = p1
        }
    }

    println("Merge result is ${dummyHead.next}")
    return dummyHead.next!!
}

fun main() {
    mergeTwoSortedLists(listNodeOf(2, 5, 7), listNodeOf(3, 11))
    mergeTwoSortedLists(listNodeOf(1, 3, 5), listNodeOf(2, 4, 6))
    mergeTwoSortedLists(listNodeOf(1, 3), listNodeOf(2, 4, 6))
    mergeTwoSortedLists(listNodeOf(1), listNodeOf(2, 4, 6))
    mergeTwoSortedLists(listNodeOf(3), listNodeOf(2, 4, 6))
    mergeTwoSortedLists(listNodeOf(7), listNodeOf(2, 4, 6))
}