using one carry queue 63ms c++ solution


  • 0
    K

    class Solution {
    public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    queue<int >k;
    ListNode* a=l1;
    ListNode* b=l2;
    ListNode* u;
    ListNode* v;
    int x=0,y=0;
    while(a->next!=NULL){a=a->next,x++;}
    while(b->next!=NULL){b=b->next,y++;}
    a=l1,b=l2;
    int set=0;
    if(x>y){for(int i=1;i<=x-y;i++)a=a->next;set=1;}
    if(x<y){for(int i=1;i<=y-x;i++)b=b->next;set=2;}
    if(x==y) set=2;
    int count=1;
    //cout<<a->val<<b->val;
    while(a!=NULL&&b!=NULL)
    {
    if((a->val+b->val)>9&&set==1){k.push(count-1+(x-y));a->val=(a->val+b->val)%10;}
    else if((a->val+b->val)>9&&set==2){k.push(count-1+(y-x));b->val=(a->val+b->val)%10;}
    else if(set==1) a->val+=b->val;
    else if(set==2) b->val+=a->val;
    a=a->next;
    b=b->next;
    count++;
    }
    int fix=0;
    ListNode* yo;
    if(!k.empty()&&k.front()==0&&set==2){ yo=new ListNode(1);yo->next=l2;k.pop();fix=1;}
    if(!k.empty()&&k.front()==0&&set==1){ yo=new ListNode(1);yo->next=l1;k.pop();fix=1;}

        while(!k.empty())
        {  cout<<k.size();
        
           if(set==1)
           {    int c=1;
                u=l1;
               int var=k.front();
               k.pop();
               while(c!=var&&u->next!=NULL)
               {    u=u->next;
                    c++;
               }    cout<<u->val;
                    if((u->val+1)>9){u->val=(u->val+1)%10;if((c-1)==0){yo=new ListNode(1);yo->next=l1;fix=1; continue;} else k.push(c-1);}
                    else
                    {u->val=u->val+1;}
           }
            if(set==2)
           {   
                int c=1;
               
                u=l2;
                int var=k.front();
                cout<<var<<"_";
            
                k.pop();
               while(c!=var&&u->next!=NULL)
               {    u=u->next;
                    c++;
               }
                if((u->val+1)>9){u->val=(u->val+1)%10;if((c-1)==0){yo=new ListNode(1);yo->next=l2;fix=1;continue;} else k.push(c-1);}
                else
                {u->val=u->val+1;}
           }
        }
        
    if(set==1&&fix==1) return yo;
    else if(set==2&&fix==1) return yo;
        if(set==1) return l1;
        else return l2;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.