版权声明

版权声明：本文为博主原创文章，转载请注明出处+地址

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

题目题解（kotlin）

解一：递归

代码源码

 private fun addTwoNode(l1: ListNode?, l2: ListNode?, hasExtra: Boolean): ListNode? {
            var resultNode: ListNode? = null
            if (l1 == null && l2 != null) {
                return if (hasExtra) {
                    resultNode = ListNode((l2.`val` + 1) % 10)
                    resultNode.next = addTwoNode(
                        null, l2.next,
                        l2.`val` + 1 >= 10
                    )
                    resultNode
                } else {
                    l2
                }
            }

            if (l2 == null && l1 != null) {
                return if (hasExtra) {
                    resultNode = ListNode((l1.`val` + 1) % 10)
                    resultNode.next = addTwoNode(
                       null, l1.next,
                        l1.`val` + 1 >= 10
                    )
                    resultNode
                } else {
                    l1
                }
            }

            if (l2 == null && l1 == null) {
                return if (hasExtra) ListNode(1) else null
            }


            var result = 0
            result = if (hasExtra) {
                (l1!!.`val` + l2!!.`val` + 1) % 10
            } else {
                (l1!!.`val` + l2!!.`val`) % 10
            }

            resultNode = ListNode(result)

            resultNode.next = addTwoNode(
                l1.next, l2.next, if (hasExtra) {
                    l1.`val` + l2.`val` + 1 >= 10
                } else {
                    (l1.`val` + l2.`val`) >= 10
                }
            )
            return resultNode
        }
    }

反思

代码写的很复杂也很冗余，思路不清晰，不停的在根据测试用例的错误结果去修正逻辑，最近看了递归的算法，就首先想到了用递归去做，做的很不理想，明天来优化一下这个递归的做法。

解二：循环

代码源码

class Sixteen2Test {

    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            val l1 = ListNode(2)
            val l1_1 = ListNode(4)
            val l1_2 = ListNode(3)

            l1.next = l1_1
            l1_1.next = l1_2

            val l2 = ListNode(5)
            val l2_1 = ListNode(6)
            val l2_2 = ListNode(4)

            l2.next = l2_1
            l2_1.next = l2_2

            addTwoNumbers(l1, l2)
        }

        fun addTwoNumbers(l1: ListNode, l2: ListNode): ListNode? {

            val headNode = ListNode(0)
            var p: ListNode? = l1
            var q: ListNode? = l2
            var result: ListNode? = headNode
            var flag: Int = 0 // 标志位：0：没有进位；1：有进位

            var pValue: Int
            var qValue: Int
            var sumValue: Int

            while (p != null || q != null) {
                pValue = p?.`val` ?: 0
                qValue = q?.`val` ?: 0
                sumValue = pValue + qValue + flag

                flag = sumValue / 10
                result?.next = ListNode(sumValue % 10)
                
                p = p?.next
                q = q?.next
                result = result?.next
            }

            if (flag > 0) {
                result?.next = ListNode(flag)
            }

            return headNode.next
        }
    }

}

反思

• 反思：这道题在做的过程中，犯了一个错误，那就是没有将最原始的node节点保存下来
• 直接对result进行操作，导致最后result指向了一个null的节点
• 改进，headNode，将其赋值给result
• 错误：其实这样子在操作result的时候也是在操作headNode，毕竟非基本类型，他们指向的存储数据的内存是同一块
• 改进：用headNode去保存头节点，但是在操作的时候，将result的next作为一个被操作对象
• 正确：将头节点保存完好，在需要打印的时候，只需要去除头节点即可，即将headNode的next进行return