C solution: linear time and O(1) space except answer itself using recursion (45ms, non-recursive)


  • 0
    M

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • struct ListNode *next;
      
    • };
      */
      int getListLength(const struct ListNode *l){
      struct ListNode *pNode = l;
      int count = 0;

      while(pNode){
      count++;
      pNode = pNode->next;
      }

      return count;
      }

    int addTwoNumbers_1(struct ListNode *l1,int len1,struct ListNode *l2,int len2){
    int carry = 0;
    int sum = 0;

    if(len1 == 0 || len2 == 0||
       l1 == NULL || l2 == NULL){
        return 0;
    }
    
    if(len1>len2){
        carry = addTwoNumbers_1(l1->next,len1-1,l2,len2);
        sum = carry + l1->val;
        l1->val = sum%10;
    }
    
    if(len1 == len2){
        carry = addTwoNumbers_1(l1->next,len1-1,l2->next,len2-1);
        sum = carry + l1->val + l2->val;
        l1->val = sum%10;
    }   
    
    if(len1<len2){
        carry = addTwoNumbers_1(l1,len1,l2->next,len2-1);
        sum = carry + l2->val;
        l2->val = sum%10;
    }
          
    carry = sum/10;
    
    return carry;
    

    }

    struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    int len1 = 0;
    int len2 = 0;
    int carry = 0;
    struct ListNode *pNode = NULL;
    struct ListNode *head = NULL;

    len1 = getListLength(l1);
    len2 = getListLength(l2);
    
    if(len1>len2){
        carry = addTwoNumbers_1(l1,len1,l2,len2);
        pNode = l1;
    }
    
    if(len1<=len2){
        carry = addTwoNumbers_1(l2,len2,l1,len1);
        pNode = l2; 
    }
    
    if(carry>0){
        head = (struct ListNode *)malloc(sizeof(struct ListNode));
        head->val = carry;
        head->next = pNode;
        pNode = head;
    }
    
    return pNode;
    

    }


Log in to reply
 

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