两数相加

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

解题思路:
  非空链表意味着一定会有加法运算,不存在直接返回某个链表的可能;逆序存储刚好符合加法低位对齐从低到高的计算顺序(正序需要压栈再计算);每个节点存储一位数字的话,契合了加法按每位运算的规则。
  先处理两条链表的加法,然后处理较长的链表剩下的数据。需要注意的是,在这个逻辑之后,还要判断进位是否为1,因为可能处理完两条链表之后还有进位值没有处理,我开始就在这上面犯了错误。

//Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
    tail := head
    carry, sum  := 0, 0

    for ; nil != l1 && nil != l2; l1, l2 = l1.Next, l2.Next {
        sum = carry + l1.Val + l2.Val
        if sum > 9 {
            carry = 1
            sum = sum - 10
        } else {
            carry = 0
        }

        node := &ListNode{
            Val:  sum,
            Next: nil,
        }
        tail.Next = node
        tail = node
    }

    for ; nil != l1; l1 = l1.Next {
        sum = carry + l1.Val
        if sum > 9 {
            carry = 1
            sum = sum - 10
        } else {
            carry = 0
        }
        node := &ListNode{
            Val:  sum,
            Next: nil,
        }
        tail.Next = node
        tail = node
    }

    for ; nil != l2; l2 = l2.Next {
        sum = carry + l2.Val
        if sum > 9 {
            carry = 1
            sum = sum - 10
        } else {
            carry = 0
        }
        node := &ListNode{
            Val:  sum,
            Next: nil,
        }
        tail.Next = node
        tail = node
    }

    //等长链表最后一位的进位
    //或者长的一条链表剩余部分是“999”数字产生进位
    if 1 == carry {
        node := &ListNode{
            Val:  1,
            Next: nil,
        }
        tail.Next = node
        tail = node
    }
    return head.Next
}

  查看题解后,发现第一个for循环的条件可以改为(nil != l1) || (nil != l2), 在循环中推进每个链表,这样只需一个循环就可以完成题目了。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 2. 两数相加 Description 给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的...
    狂吃不胖温同学阅读 837评论 0 1
  • 题目:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个...
    anloney阅读 1,150评论 1 0
  • 题目 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个...
    李_秋_实阅读 293评论 0 0
  • “低质量的恋爱不如高质量的单身”,今天学到的一句话,不知道什么叫三观不合,但当你想吃一块星巴克蛋糕而他告诉你一顿星...
    倔强的萝卜呀阅读 481评论 0 0
  • 为何爱会伤人,这算一本心理相关的书吧,真是了解了很多之前根本不会想到的东西,我不一定觉得它说的都正确,但拿这些知识...
    新月饭店大小姐阅读 156评论 0 0