算法：两个单链表生成相加链表

算法

版本：2
作者：陈小默
声明：禁止商业，禁止转载

发布于作业部落、SCDN

题目：假设链表中的每一节点的值都在0~9之间，于是我们可以使用整个链表作为一个整数。
例如：

链表9->3->7和链表6->3相加后得到链表1->0->0->0

解法：我们可以先将两个链表转置，然后从低位到高位依次运算。

一下代码给出了三种实现方式，后一种是前一种的简化

data class Node(var value: Int, var next: Node?) {
    override fun toString(): String {
        val builder = StringBuilder().append('[')
        var node: Node? = this.next
        builder.append(value)
        while (node != null) {
            builder.append(',').append('\t').append(node.value)
            node = node.next
        }
        return builder.append(']').toString()
    }
}
fun reverseList(list: Node): Node {
    var pre: Node? = null
    var next: Node? = null
    var head: Node? = list
    while (head != null) {
        next = head.next
        head.next = pre
        pre = head
        head = next
    }
    return pre!!
}
fun addList_v1(list1: Node, list2: Node): Node {
    var l1: Node? = reverseList(list1)
    var l2: Node? = reverseList(list2)
    var next: Node? = null
    var node: Node?
    var head: Node? = null
    var carry = false
    while (l1 != null && l2 != null) {
        var value = l1.value + l2.value
        if (carry) value++
        carry = value > 9
        if (carry) value %= 10
        node = Node(value, null)
        if (head == null) {
            head = node
            next = node
        } else {
            next!!.next = node
            next = next.next
        }
        l1 = l1.next
        l2 = l2.next
    }
    while (l1 != null) {
        var value = l1.value
        if (carry) value++
        carry = value > 9
        if (carry) value %= 10
        node = Node(value, null)
        if (head == null) {
            head = node
            next = node
        } else {
            next!!.next = node
            next = next.next
        }
        l1 = l1.next
    }
    while (l2 != null) {
        var value = l2.value
        if (carry) value++
        carry = value > 9
        if (carry) value %= 10
        node = Node(value, null)
        if (head == null) {
            head = node
            next = node
        } else {
            next!!.next = node
            next = next.next
        }
        l2 = l2.next
    }
    if (carry) {
        node = Node(1, null)
        next!!.next = node
    }
    return reverseList(head!!)
}
fun addList_v2(list1: Node, list2: Node): Node {
    var l1: Node? = reverseList(list1)
    var l2: Node? = reverseList(list2)
    var next: Node?
    var head: Node? = null
    var carry = 0
    while (l1 != null && l2 != null) {
        val value = l1.value + l2.value + carry
        carry = value / 10
        next = head
        head = Node(value % 10, next)
        l1 = l1.next
        l2 = l2.next
    }
    while (l1 != null) {
        val value = l1.value + carry
        carry = value / 10
        next = head
        head = Node(value % 10, next)
        l1 = l1.next
    }
    while (l2 != null) {
        val value = l2.value + carry
        carry = value / 10
        next = head
        head = Node(value % 10, next)
        l2 = l2.next
    }
    if (carry == 1) {
        next = head
        head = Node(1, next)
    }
    return head!!
}
fun addList(list1: Node, list2: Node): Node {
    var l1: Node? = reverseList(list1)
    var l2: Node? = reverseList(list2)
    var n: Int
    var n1: Int
    var n2: Int
    var next: Node?
    var head: Node? = null
    var carry = 0
    while (l1 != null || l2 != null) {
        n1 = if (l1 != null) l1.value else 0
        n2 = if (l2 != null) l2.value else 0
        n = n1 + n2 + carry
        carry = n / 10
        next = head
        head = Node(n % 10, next)
        l1 = if (l1 != null) l1.next else null
        l2 = if (l2 != null) l2.next else null
    }
    if (carry == 1) {
        next = head
        head = Node(1, next)
    }
    return head!!
}