O(n) Time, O(1) Space, C++


  • 0
    class Solution {
    private:
        int getLength (ListNode *head) {
            int n = 0;
            while (head) {
                head = head->next;
                ++n;
            }
            return n;
        }
        ListNode *reverse(ListNode *head) {
            ListNode newHead(0);
            while (head) {
                ListNode *p = head;
                head = head->next;
                p->next = newHead.next;
                newHead.next = p;
            }
            return newHead.next;
        }
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode *head = NULL;
            int n1 = getLength(l1), n2 = getLength(l2);
            if (n1 < n2) {
                swap(l1, l2);
                swap(n1, n2);
            }
            while (n1 > n2) {
                ListNode *p = new ListNode(l1->val);
                p->next = head;
                head = p;
                l1 = l1->next;
                --n1;
            }
            while (l1) {
                int carry = l1->val + l2->val;
                ListNode *p = new ListNode(carry % 10);
                p->next = head;
                head = p;
                while (carry /= 10) { // propagate the carry
                    if (p->next) {
                        carry += p->next->val;
                        p->next->val = carry % 10;
                        p = p->next;
                    } else {
                        p->next = new ListNode(carry);
                    }
                }
                l1 = l1->next;
                l2 = l2->next;
            }
            return reverse(head);
        }
    };
    

    For example:

    Input: 
    l1: (1 -> 9 -> 4 -> 4)
    l2: (5 -> 6)
    
    // Step 1. Copy nodes of the leading parts in l1, reversely
    l1: (4->4)
    l2: (5->6)
    ans: (9->1)
    
    // Step 2. Add nodes in l1 and l2, and propagate the carry.
    l1: (4)
    l2: (6)
    ans: (9->9->1) (the first 9 = 4 + 5, no carry)
    
    l1: ()
    l2: ()
    ans: (10->9->9->1) (the first 10=4+6, propagate the carry)
    ans: (0->10->9->1)
    ans: (0->0->0->2)
    
    // Step3. reverse ans
    

Log in to reply
 

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