2. 两数相加（中等）

• 难度: 中等
• 考察: 数组
• 来源: https://leetcode-cn.com/problems/add-two-numbers/description/
• 题解: https://github.com/azl397985856/leetcode/blob/master/problems/2.addTwoNumbers.md

题目

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

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

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

示例:

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

思路

设立一个表示进位的变量carried，建立一个新链表，把输入的两个链表从头往后同时处理，每两个相加，将结果加上carried后的值作为一个新节点到新链表后面。

关键点

• 链表数据结构的特点和使用
• 用一个carried变量来实现进位的功能，每次相加之后计算carried，并用于下一位的计算

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(N)

代码

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1.Val == 0 && l1.Next == nil{
        return l2
    }
    if l2.Val == 0 && l2.Next == nil{
        return l1
    }
    var head, result *ListNode
    carried := 0
    for l1 != nil || l2 !=nil || carried > 0{
        val := carried
        if l1 !=nil{
            val += l1.Val
            l1 = l1.Next
        }
        if l2 !=nil {
            val += l2.Val
            l2 = l2.Next
        }

        carried = val/10
        if result == nil{
            result = &ListNode{Val: val%10}
            head = result
        }else{
            result.Next = &ListNode{Val: val%10}
            result = result.Next
        }
    }
    return head