C solved,but the runtime in C is not fast (20ms)


  • 0
    H

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • struct ListNode *next;
      
    • };
      */
      typedef struct ListNode ListNode;

      struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)

    {

                   ListNode* l;
                   l=NULL;
                   ListNode* newp;
                   ListNode* tail;
                   tail=NULL;
                   ListNode* r;
                   ListNode* s;
                   r=l1;
                   s=l2;
                   int lenth1,lenth2,i;
                   lenth1=0;
                   lenth2=0;
                   ListNode* t1;
                   ListNode* t2;
                  while(r!=NULL)
                      {lenth1++;t1=r;r=r->next;}
                  while(s!=NULL)
                      {lenth2++;t2=s;s=s->next;}
                  r=l1;
                  s=l2;
                  int e;
                  int h=0;
                  if(l1==NULL) return l2;
                  else if(l2==NULL) return l1;
                  else
                       {
                             if(lenth1>lenth2)
                             {
                                  for(i=0;i<(lenth1-lenth2);i++)
                                  {
                                   newp=(ListNode*)malloc(sizeof(ListNode));
                                   newp->val=0;
                                   t2->next=newp;
                                   t2=t2->next;
                                   }
                             }
                            if(lenth1<lenth2)
                            {
                              for(i=0;i<(lenth2-lenth1);i++)
                              {
                               newp=(ListNode*)malloc(sizeof(ListNode));
                               newp->val=0;
                               t1->next=newp;
                               t1=t1->next;
                               }  
                            }
                            while(r&&s)                    
                            {
                              e=r->val+s->val+h;
                              newp=(ListNode*)malloc(sizeof(ListNode));
                              h=e/10;
                              newp->val=e%10;
                              if(l==NULL) l=newp;
                              else tail->next=newp;
                              tail=newp;            
                              s=s->next;
                              r=r->next;
                            }
                           if(h!=0)
                           {
                             newp=(ListNode*)malloc(sizeof(ListNode));
                             newp->val=h;
                             if(l==NULL) l=newp;
                             else tail->next=newp;
                             tail=newp;
                            }
                           tail->next=NULL;
                           return l;
                      }
    

    }


  • 0
    A

    @hljsrc It looks ok asymptotically, but you could avoid some of the computation. You are iterating through the input lists to get the length, and then allocating space memory for the difference between the lists, but none of this is necessary.
    Just deal with different length inputs on the fly, in the last while loop.

    Note also that while getting the lengths of the input lists (and the tails), you are assigning t1=r; in the while loop, and this would not be needed anyway.


  • 0
    H

    @alejandroerickson

    Thank you for reminding, got it,


Log in to reply
 

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