LeetCode-两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

  1.先将两个链表反转，转为两个数然后相加，再转成链表

  /**
   * 先将两个链表反转，相加后，再转为链表
   */
  def solution1(first: Node, second: Node): Node = {
       var resNum = inverse(first, "").toInt + inverse(second, "").toInt
       val head = Node(0, null)
       var cur = head
       while (resNum / 10 != resNum) {
            cur.next = Node(resNum % 10, null)
            cur = cur.next
            resNum = resNum / 10
       }
       head.next
  }
  
  /**
   * 链表反转为字符串
   */
  def inverse(node: Node, res: String): String = {
       if (node.next == null) {
            res + node.value
       } else {
            inverse(node.next, res) + node.value
       }
  }

2.按加法原理直接相加

/**
 * 直接相加，大于10进1
 */
def solution2(first: Node, second: Node): Node = {
     val head: Node = Node(0, null)
     var canary = 0
     var t1:Node = first
     var t2:Node = second
     var cur = head
     while (t1 != null || t2 != null) {
          val v1 = if(t1 == null) 0 else t1.value
          val v2 = if(t2 == null) 0 else t2.value
          val tmp = v1 + v2 + canary
          cur.next = Node(tmp % 10, null)
          cur = cur.next
          canary = tmp / 10
          t1 = if(t1.next == null) null else t1.next
          t2 = if(t2.next == null) null else t2.next
     }

     if(canary > 0){
          cur.next = new Node(canary, null)
     }

     head.next
}