两个有序的链表合并

考虑先定义一个空的链表头 emptyHead ，最后只需返回 emptyHead.next 就可以，比较简单。

/**
 * 链表数据结构
 */
class Node constructor(val data: Char) {
    var next: Node? = null

    override fun toString(): String {
        val sb = StringBuilder()
        sb.append(data)
        var tmp: Node? = next
        while (tmp != null) {
            sb.append(tmp.data)
            tmp = tmp.next
        }
        return sb.toString()
    }
}

//为了测试方便，将字符转换为链表来存储
fun toLinkedListStr(str: String?): Node? {
    if (str.isNullOrEmpty())
        return null
    var head: Node? = null
    var next: Node? = null
    for (ch in str) {
        val node = Node(ch)
        next?.next = node
        next = node
        if (head == null) {
            head = node
            next = node
        }
    }
    return head
}

//合并2个链表
fun mergeTwoLinkedList(node1: Node?, node2: Node?): Node? {
    node1 ?: return node2
    node2 ?: return node1
    var emptyHead = Node('0')
    var first = node1
    var second = node2
    var current: Node? = emptyHead
    while (first != null && second != null) {
        val v1 = first.data
        val v2 = second.data
        if (v1 <= v2) {
            current?.next = first
            first = first.next
        } else {
            current?.next = second
            second = second.next
        }
        current = current?.next
        current?.next = null
        if (first == null) {
            //第一个链表为空了，直接链上第2个链表
            current?.next = second
        } else if (second == null){
            current?.next = first
        }
    }
    return emptyHead.next
}

fun main() {
    val str1 = toLinkedListStr("024689")
    val str2 = toLinkedListStr("135789")
    println(mergeTwoLinkedList(str1, str2))
}

合并的结果如下：

012345678899