Intuitive C++ Solution, without stacks, reversing, recursion, etc.


  • 0
    A

    Hi, Here's my solution in C++ without stacks, reversing and recursion. It only takes more time...
    Any suggestion to make it better? Thanks. :)

    // 49ms
    
    ListNode* GetNode(ListNode *l, int pos) {
        if (!l || pos <= 0) return l;
    
        pos--;
    
        while (pos--) {
            l = l->next;
            if (!l) break;
        }
    
        return l;
    }
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (!l1 && !l2) return NULL;
        if (!l1) return l2;
        if (!l2) return l1;
    
        int len1 = 0, len2 = 0, carry = 0;
        ListNode *p1 = l1, *p2 = l2;
    
        // Get the total length of each list
        while (p1) {
            len1++;
            p1 = p1->next;
        }
        while (p2) {
            len2++;
            p2 = p2->next;
        }
    
        // Sum digits form tail, save the result to l1
        while (len1 || len2) {
            if (!len1) {
                ListNode *tmp = new ListNode(GetNode(l2, len2)->val + carry);
                tmp->next = l1;
                l1 = tmp;
            }
            else if (!len2) {
                GetNode(l1, len1)->val += carry;
            }
            else {
                GetNode(l1, len1)->val += (carry + GetNode(l2, len2)->val);
            }
    
            // Handle carry
            if (GetNode(l1, len1)->val >= 10) {
                GetNode(l1, len1)->val %= 10;
                carry = 1;
            }
            else
                carry = 0;
    
            if (len1) len1--;
            if (len2) len2--;
        }
    
        if (carry) {
            ListNode *tmp = new ListNode(1);
            tmp->next = l1;
            l1 = tmp;
        }
    
        return l1;
    }
    

Log in to reply
 

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