专栏首页GoLang那点事链表-两数相加

链表-两数相加

问题

给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储一位数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 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,从前往后放结果是不是反转也不需要了,直接就是答案了?确实如此,如第二张图


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

type ListNode struct {
   Next *ListNode
   Val int
}

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

func buildArray(node1 *ListNode, node2 *ListNode) ([]int ,[]int ) {
   array1 := make([]int,0)
   array2 := make([]int,0)
   for node1 != nil{
      array1 = append(array1,node1.Val)
      node1 = node1.Next
   }
   for node2 != nil{
      array2 = append(array2,node2.Val)
      node2 = node2.Next
   }
   l := len(array1)
   r := len(array2)
      // 如果array1的长度小于array2的长度,那么array1补0,直到和array2相等
   for l < r{
      array1 = append(array1,0)
      l++
   }
   // 如果array2的长度小于array1的长度,那么array2补0,直到和array1相等
   for r < l{
      array2 = append(array2,0)
      r++
   }
   return array2,array1
}

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

func sumArray(array1 []int, array2 []int) []int {
     //新的数组(长度为原数组长度+1,因为两个三位数相加的和可能是4位数)
   result := make([]int,len(array1)+1)
  //temp变量是新数组的下标,从0开始
   for i,temp:=0,0;i<len(array1); i++{
            //对两个数组相加
      sum := array1[i]+array2[i]
      //想一想为啥sum又要加上新数组的下标呢?
      sum = result[temp] + sum
      if sum < 10{
         result[temp] = sum
         temp++
         continue
      }
          //如果大于10,需要往上进一位
     //把个位数字放入当前位置
      result[temp] = int(sum % 10)
     //把十位数字放入下一个位置,所有才有上面的sum = result[temp]+sum
      result[temp+1] = int(sum / 10) 
      temp++
   }
   return result
}

最后我们对结果进行组装成一个新的链表

func createNewListNode(result []int) *ListNode {
   var head,m *ListNode = nil,nil
   for i:=0;i<len(result);i++{
      if result[i] ==0 && i == len(result)-1{
         break
      }
      if m== nil{
         m = &ListNode{Val:result[i],Next:nil}
         head = m
         continue
      }
      m.Next = &ListNode{Val:result[i],Next:nil}
      m = m.Next
   }
   return head
}

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

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

解法二

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

递归入参是,node1,node2, result[]int (存储链表节点的值的和),carry(进位的值)

func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode{
   result := make([]int,0)
    //递归求值
   result =  sumListNode(l1,l2,result,0)
   var head,temp *ListNode = nil,nil
    // 组装新的链表
   for i:=0;i<len(result);i++{
      if temp == nil{
         temp = &ListNode{Val:int(result[i]),Next:nil}
         head = temp
         continue
      }
      temp.Next = &ListNode{Val:result[i],Next:nil}
      temp = temp.Next
   }
   return head;
}
func sumListNode(node1 *ListNode, node2 *ListNode, result []int,carry int) []int {
    //当两个节点都为空,计算完毕
   if node1 == nil && node2 == nil{
      //判断节点最后的和进位是否有值
      if carry != 0{
         result = append(result,carry)
      }
      return result
   }
    //两个节点的值初始都置为0(跟解法一中链表构造数组长度不一致补0是一个思路)
   l1,l2 := 0,0
   if node1 != nil{
        //重新赋值
      l1 = node1.Val
      node1 = node1.Next
   }
   if node2 != nil{
        //重新赋值
      l2 = node2.Val
      node2 = node2.Next
   }
    //求和
   temp := l1 + l2 + carry
    //取域
   remainder := temp % 10
    //求商(也是进位,大于10是进位是1,否则是0)
   carry = temp / 10
    //将求的和放入数组中
   result = append(result,remainder)
    //递归求两个链表的下一个节点的和
   return sumListNode(node1,node2,result,carry)
}

最后,希望大家有所收获,如果大家有更好的思路可以留言交流,同时大家可以思考下这两种方法的空间复杂度和时间复杂度。

本文分享自微信公众号 - GoLang那点事(aweiaichitudou)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表-快速寻找链表中的下一个更大节点?你怎么做

    阿伟
  • Go指针,如此轻松掌握,希望有收获

    阿伟
  • Go指针,如此轻松掌握

    依稀记得大学必修课,C语言中的指针,简直是噩梦,指来指去,有没有晕乎乎的感觉,我在想是不是也因为如此,所以Java语言的开发者才比C语言的多,Ja...

    阿伟
  • 关于HashMap的一些理解

    本文主要补充对HashMap的一些理解、分析。相信大家对HashMap都很熟悉,但是其中的一些细节上的设计、思想,往往会被大家忽略,这些都是构成HashMap的...

    Erwin
  • 小程序版 QQ 推出 / 微信新增「语音加速功能」与「夜间模式」| 晓技巧

    知晓君
  • ios设备突破微信小视频6S限制的方法

      刷微信朋友圈只发文字和图片怎能意犹未竟,微信小视频是一个很好的补充,音视频到位,流行流行最流行。但小视频时长不能超过6S,没有滤镜等是很大的遗憾。but有人...

    ytkah
  • 谈谈 MVC 模式

    如何设计一个程序的结构,这是一门专门的学问,叫做"架构模式"(architectural pattern),属于编程的方法论。

    IT派
  • 谈谈MVC模式

    1. 如何设计一个程序的结构,这是一门专门的学问,叫做"架构模式"(architectural pattern),属于编程的方法论。 MVC模式就是架构模式的一...

    MonroeCode
  • 谈谈MVC模式

    1. 如何设计一个程序的结构,这是一门专门的学问,叫做"架构模式"(architectural pattern),属于编程的方法论。 MVC模式就是架构模式的一...

    ruanyf
  • 单向链表的一点儿感悟

    最近一段时间学习了挺多的,数据结构看了一点点,略有感悟,和感兴趣的同志分享一下,欢迎大家不吝评论。

    用户5908113

扫码关注云+社区

领取腾讯云代金券