2. 两数相加

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

type ListNode struct {
	Val  int
	Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	resPre := &ListNode{}
	cur := resPre
	carry := 0

	for l1 != nil || l2 != nil || carry > 0 {
		sum := carry

		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}

		carry = sum / 10

		cur.Next = &ListNode{Val: sum % 10}
		cur = cur.Next
	}

	return resPre.Next
}

// 递归实现
func addTwoNumbers2(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumber(l1, l2, 0)
}

func addTwoNumber(l1 *ListNode, l2 *ListNode, add int) *ListNode{
    if l1 == nil && l2 == nil && add == 0 {
        return nil;
    }

    if l1 != nil {
        add += l1.Val
        l1 = l1.Next
    }
    if l2 != nil {
        add += l2.Val
        l2 = l2.Next
    }

    node := ListNode{
        Val: add % 10,
        Next: addTwoNumber(l1, l2, add / 10),
    }

    return &node
}