2. Add Two Numbers

problem description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

algorithm thought

观察知道，题目需要返回一个相加之后的链表。碰到链表题以及树类题目，尤其是返回一个链表或者树的时候，大概律用递归做会简单很多。

用递归的思想去解题的话，首先想好每一个递归节点是如何设计的，然后设计好递归基处理结束清况。其实很类似数学归纳法。对于链表相加问题，将每个函数看成累加器的中的一个寄存器就行。每个节点的输入是两个数，还有前一个节点的进位。相加得到当前节点的值，将进位传给下一个函数。

code

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2,int add=0) {
        if(l1==NULL){
            if(add==0)
                return l2;
            l1=new ListNode(add);
            return addTwoNumbers(l1,l2,0);
        }else if(l2==NULL){
            if(add==0)
                return l1;
            l2=new ListNode(add);
            return addTwoNumbers(l1,l2,0);
        }//上面是递归基
        ListNode* res=new ListNode((l1->val+l2->val+add)%10);
        res->next=addTwoNumbers(l1->next,l2->next,(l1->val+l2->val+add)/10);
        return res;
    }
};

algorthm analysis

时间应该可以认为是O(n)，遍历一个链表。

虽然递归函数会在调用栈上消耗很多时间，相比于迭代解题会慢一点。但是递归函数比迭代更容易写，需要考虑的情况会少很多，并且大多数情况下其实慢不了太多。所以链表题和树题建议先考虑递归解法