题解 | #两个链表生成相加链表#

题解一：递归
首先遍历两个链表求出长度len1，len2, 并且head1永远指向长度较长的那个链表。
递归分析：
递归边界： head1 == NULL;
递归过程：
情况1： len1>len2 表明没有到首位相加位数只需add(head1->next,head2)
情况2： add(head1->next,head2->next);
回溯过程：
情况1：len1>len2 sum = jin+head1->val;
情况2： sum = jin + head1->val+head2->val;
图示：

复杂度分析：
时间复杂度： $O(M+N)$ ：需要统计两个链表的长度
空间复杂度： $O(max(M,N))$ :递归次数是两个链表中的最大长度

实现如下：

class Solution {
public:
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    int add_list(ListNode* head1,ListNode* head2,int len1,int len2){
        if(head1==NULL) return 0;  // 递归边界
        int jin,sum; 
        //len1>len2  head1->next;
        if(len1>len2) {  
            jin = add_list(head1->next, head2, len1-1, len2);
            sum =  jin + head1->val;
        }else{
            jin = add_list(head1->next, head2->next, len1-1, len2-1);
            sum = jin+head1->val+head2->val;
        }
        head1->val = sum%10;
        return sum/10;  //返回进位
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        int len1 = 0;
        int len2 = 0;
        ListNode* p = head1;
        ListNode* q = head2;
        while(p) {len1++; p = p->next;}
        while(q) {len2++; q = q->next;}
        //head1永远指向长度长的
        if(len1<len2){
            ListNode* t = head1;
            head1 = head2;
            head2 = t;
            int tt = len2;
            len2 = len1;
            len1 = tt;
        }
        ListNode* start = new ListNode(0); //创建一个节点指向head1
        start->next = head1;
        start->val = add_list(head1, head2, len1, len2);
        if(start->val) return start;  //最高位有进位
        return start->next;
    }
};

题解二：使用栈
题解思路：利用栈先进后出原则，保存链表元素，从而实现低位相加进位到高位。
复杂度分析：
时间复杂度： $O(M+N)$ ,需要遍历两个链表的长度
空间复杂度： $O(M+N)$ ，申请了两个栈，最差情况，将两个链表都保存在两个栈中
实现如下：

class Solution {
public:
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
ListNode* addInList(ListNode* head1, ListNode* head2) {
stack<ListNode*> s1;  //保存head1的节点
        stack<ListNode*> s2;   //保存head2的节点
        ListNode* p = head1;
        ListNode* q = head2;
        while(p||q){
            if(p){
                s1.push(p);
                p = p->next;
            }
            if(q){
                s2.push(q);
                q = q->next;
            }
        }
        //将结果保存在head1中，所以head1依旧指向两者长的
        int ok = 0;
        if(s1.size()<s2.size()) {
            swap(head1, head2);
            ok = 1;
        }
        ListNode* start = new ListNode(0);
        start->next = head1;
        int jin = 0;
        while(!s1.empty()&&!s2.empty()){
             ListNode* add1 = s1.top(); s1.pop();
             ListNode* add2 = s2.top(); s2.pop();
             int sum = add1->val + add2->val+jin;
             //相加之后的结果保存在head1
             if(!ok)
                 add1->val = sum%10;
             else add2->val = sum%10;
             jin = sum/10;
        }
        //还有节点就看有没有进位，没有进位直接返回
        while(!s1.empty()&&jin!=0){
            ListNode* add1 = s1.top();s1.pop();
            int sum = add1->val+jin;
            add1->val = sum%10;
            jin = sum/10;
        }
        while(!s2.empty()&&jin!=0){
            ListNode* add2 = s2.top();s2.pop();
            int sum = add2->val+jin;
            add2->val = sum%10;
            jin = sum/10;
        }
                //最高位有没有进位
        if(jin) {start->val = jin;return start;}
        return start->next;
    }
};