<leetcode c++> 445. 两数相加 II

445. 两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7

非常容易想到的方法是用栈分别存储两条链表，再用头插法新建出答案要求的链表，代码如下：

ListNode* insertFromHead(ListNode* head,int k){
        ListNode* t=new ListNode(k);
        if(head!=NULL)
            t->next=head;
        return t;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> st1,st2;
        while(l1){
            st1.push(l1->val);
            l1=l1->next;
        }
        while(l2){
            st2.push(l2->val);
            l2=l2->next;
        }
        int c=0;
        ListNode* res=NULL;
        while(!st1.empty()||!st2.empty()||c!=0){
            int sum=0;
            if(!st1.empty()){
                sum+=st1.top();
                st1.pop();
            }
            if(!st2.empty()){
                sum+=st2.top();
                st2.pop();
            }
            sum+=c;
            c=sum/10;
            res=insertFromHead(res,sum%10);
        }
        return res;
    }

另一种做法就是递归，本来我觉得递归消耗的空间复杂度应该少一些的，结果可能递归本身占用的空间有点多，实际效果和上面差不多，但是思路还是很值得考量的：

void addTwo(ListNode* l1,ListNode* l2, ListNode* flag, int& k){
        if(l1==NULL||l2==NULL)
            return;
        int sum;
        if(l1==flag){
            flag=flag->next;
            addTwo(l1->next,l2->next,flag,k);
            sum=l1->val+l2->val+k;
        }
        else{
            addTwo(l1->next,l2,flag,k);
            sum=l1->val+k;
        }
        l1->val=sum%10;
        k=sum/10;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* flag1=l1;
        ListNode* flag2=l2;
        int len1=0,len2=0;
        while(flag1){
            flag1=flag1->next;
            len1++;
        }
        while(flag2){
            flag2=flag2->next;
            len2++;
        }
        int k=0;
        int c=len1-len2;
        if(c<=0){
            ListNode* tmp=l2; l2=l1; l1=tmp;
            c=0-c;
        }
        flag1=l1;
        while(c--)
        {
            flag1=flag1->next;
        }　　
        addTwo(l1,l2,flag1,k);　　//前面的准备工作一个是保证L1长于L2，二是使较短的L2的最高位与flag对齐
        if(k==1){
            ListNode* h=new ListNode(1);
            h->next= l1;
            return h;
        }
        else
            return l1;
        return NULL;
    }