• 美团北斗计划推荐算法工程师一面——2020.08.03 15:00

小水题，但要求必须A掉，主要考虑下进位和链表翻转即可。当然可以不用vector，直接把两个链表反转后模拟就行，但我不太喜欢写链表。

class Solution {
public:
    
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        vector<int>a,b;
        ListNode *now=head1;
        while(now!=NULL){
            a.push_back(now->val);
            now=now->next;
        }
        now=head2;
        while(now!=NULL){
            b.push_back(now->val);
            now=now->next;
        }
        vector<int>ans;
        int len1=(int)a.size()-1, len2=(int)b.size()-1;
        int pre=0;
        while(1){
            int cnt=0;
            if(len1==-1&&len2==-1){
                if(pre)ans.push_back(1);
                break;
            }
            else if(len1==-1){
                cnt=b[len2]+pre;
                len2--;
            }
            else if(len2==-1){
                cnt=a[len1]+pre;
                len1--;
            }
            else {
                cnt=a[len1]+b[len2]+pre;
                len1--;
                len2--;
            }
            if(cnt>9){
                pre=1;
                cnt=cnt%10;
            }
            else 
                pre=0;
            ans.push_back(cnt);
        }
        ListNode *new_head=new ListNode(ans[0]);
        ListNode *p=new_head;
        for(int i=1;i<(int)ans.size();i++){
            ListNode *node= new ListNode(ans[i]);
            p->next=node;
            p=p->next;
        }
        ListNode *pre_node=NULL;
        while(new_head){
            ListNode *reverse_node=new_head->next;
            new_head->next=pre_node;
            pre_node=new_head;
            new_head=reverse_node;
        }
        return pre_node;
        // write code here
    }
};