创建时间： 2019/8/8 9:52
作者： sunpengwei1992@aliyun.com

问题

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

示例

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

在看解法之前，请大家先思考下，自己该怎么解决呢

解法一

我们看题目和上面示例，很明显能得到下面一张图，上面示例是342+465，那么得是先从2+5=7，放入新链表的末尾，以此向下进行，放入新链表的头部，遇到相加大于10的进1。最后对链表反转得到的结果就是正确答案，我们接着看，2+5=7，4+6=10进1，3+4+1 =8，从前往后放结果是不是反转也不需要了，直接就是答案了？确实如此，得到如右图所示

链表-如快速将两个链表快速相加得到一个新的链表 - 图1

链表-如快速将两个链表快速相加得到一个新的链表 - 图2

  • 下面我们开始进入编程思路，首先声明一个链表

    1. type ListNode struct {
    2.      Next *ListNode
    3.      Val int
    4. }

  • 我们想到链表相加不太友好，而且考虑到两个链表长度不一样呢（比如A链表 1->2->3, B链表 4->5），所以我将链表转化为数组，长度短的补零，如举例的AB链表转化后，如下图

链表-如快速将两个链表快速相加得到一个新的链表 - 图3

  1. func buildArray(node1 *ListNode, node2 *ListNode) ([]int ,[]int ) {
  2.        array1 := make([]int,0)
  3.        array2 := make([]int,0)
  4.        for node1 != nil{
  5.               array1 = append(array1,node1.Val)
  6.               node1 = node1.Next
  7.        }
  8.        for node2 != nil{
  9.               array2 = append(array2,node2.Val)
  10.               node2 = node2.Next
  11.        }
  12.        l := len(array1)
  13.        r := len(array2)
  14.           // 如果array1的长度小于array2的长度，那么array1补0，直到和array2相等
  15.        for l < r{
  16.               array1 = append(array1,0)
  17.               l++
  18.        }
  19.        // 如果array2的长度小于array1的长度，那么array2补0，直到和array1相等
  20.        for r < l{
  21.               array2 = append(array2,0)
  22.               r++
  23.        }
  24.        return array2,array1
  25. }

  • 接着我们按照分析对数组进行相加，得到一个新的数组，考虑一下，新数组的长度考虑建多长呢？两个三位数相加（999+999 = 1998），最大是4位数，所以新数组的长度永远比原来数组的长度大1就可以，看代码：

    1. func sumArray(array1 []int, array2 []int) []int {
    2.      //新的数组（长度为原数组长度+1，因为两个三位数相加的和可能是4位数）
    3.      result := make([]int,len(array1)+1)
    4.     //temp变量是新数组的下标,从0开始
    5.      for i,temp:=0,0;i<len(array1); i++{
    6.              //对两个数组相加
    7.             sum := array1[i]+array2[i]
    8.             //想一想为啥sum又要加上新数组的下标呢？
    9.             sum = result[temp] + sum
    10.             if sum < 10{
    11.                    result[temp] = sum
    12.                    temp++
    13.                    continue
    14.             }
    15.                 //如果大于10，需要往上进一位
    16.            //把个位数字放入当前位置
    17.             result[temp] = int(sum % 10)
    18.            //把十位数字放入下一个位置，所有才有上面的sum = result[temp]+sum
    19.             result[temp+1] = int(sum / 10) 
    20.             temp++
    21.      }
    22.      return result
    23. }

  • 再者我们对结果进行组装成一个新的链表

    1. func createNewListNode(result []int) *ListNode {
    2.      var head,m *ListNode = nil,nil
    3.      for i:=0;i<len(result);i++{
    4.             if result[i] ==0 && i == len(result)-1{
    5.                   break
    6.             }
    7.             if m== nil{
    8.                    m = &ListNode{Val:result[i],Next:nil}
    9.                    head = m
    10.                    continue
    11.             }
    12.             m.Next = &ListNode{Val:result[i],Next:nil}
    13.             m = m.Next
    14.      }
    15.      return head
    16. }

  • 最后对上面三个步骤组合，得到结果

    1. func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    2.      //把链表构造为两个数组
    3.      array1,array2 := buildArray(l1,l2)
    4.      //对数组相加
    5.      result := sumArray(array1,array2)
    6.      //组装新的链表
    7.      return createNewListNode(result)
    8. }

    解法二

    看完上面的解法一，为什么这么复杂？脑袋疼，想不过来，不想学算法了，有没有更简单的，解法二带你体验算法的神奇魅力。从解法一我们得知是从链表头部开始相加，所得结果最后作为新链表的头部，如果大于10，则向上进一位，在创建新链表下一个节点时把进上来的值加上，依次直到两个链表的节点都为空，基于这个我们考虑能不能用递归呢？ 递归入参是，node1，node2， result[]int (存储链表节点的值的和)，carry(进位的值)

  1. func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode{
  2.        result := make([]int,0)
  3.         //递归求值
  4.        result =  sumListNode(l1,l2,result,0)
  5.        var head,temp *ListNode = nil,nil
  6.         // 组装新的链表
  7.        for i:=0;i<len(result);i++{
  8.               if temp == nil{
  9.                      temp = &ListNode{Val:int(result[i]),Next:nil}
  10.                      head = temp
  11.                      continue
  12.               }
  13.               temp.Next = &ListNode{Val:result[i],Next:nil}
  14.               temp = temp.Next
  15.        }
  16.        return head;
  17. }
  18. func sumListNode(node1 *ListNode, node2 
  19.                     *ListNode, result []int,carry int) []int {
  20.         //当两个节点都为空，计算完毕
  21.        if node1 == nil && node2 == nil{
  22.               //判断节点最后的和进位是否有值
  23.               if carry != 0{
  24.                  result = append(result,carry)
  25.               }
  26.               return result
  27.        }
  28.         //两个节点的值初始都置为0(跟解法一中链表构造数组长度不一致补0是一个思路)
  29.        l1,l2 := 0,0
  30.        if node1 != nil{
  31.                 //重新赋值
  32.               l1 = node1.Val
  33.               node1 = node1.Next
  34.        }
  35.        if node2 != nil{
  36.                 //重新赋值
  37.               l2 = node2.Val
  38.               node2 = node2.Next
  39.        }
  40.         //求和
  41.        temp := l1 + l2 + carry
  42.         //取域
  43.        remainder := temp % 10
  44.             //求商（也是进位，大于10是进位是1，否则是0）
  45.        carry = temp / 10
  46.         //将求的和放入数组中
  47.        result = append(result,remainder)
  48.         //递归求两个链表的下一个节点的和
  49.        return sumListNode(node1,node2,result,carry)
  50. }

欢迎大家关注微信公众号：“golang那点事”，更多精彩期待你的到来
GoLang公众号.jpg