32ms C++ no reverse, no extra space, no change to original lists


  • 0
    H

    Just use a pointer to save the last non-9 digit which can take a possible carry generated by less significant bits.

    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode* head = new ListNode(0);
            ListNode* tail = head;
            ListNode* cur = head; // use to store the last node which value is less than 9
            ListNode* h1 = l1;
            ListNode* h2 = l2;
            // find the node which will be used to do alignment on addition 
            while (h1 && h2) {
                h1 = h1->next;
                h2 = h2->next;
            }
            ListNode* t; // the node as alignment marker
            if (h1) { t = h1; h1 = l1; h2 = l2; } // set h1 to the longer one's head
            else { t = h2; h1 = l2; h2 = l1; } // set h2 to the shorter one's head
            while (h1) {
                int val = h1->val;
                h1 = h1->next;
                if (t) t = t->next; // if t is not NULL, h1 is still ahead of h2
                else { // t == NULL, should add h2's value
                    val += h2->val;
                    h2 = h2->next;
                }
                if (val >= 10) {
                    val %= 10;
                    cur->val++; // take the carry value, because the original val is less than 9, no impact to previous nodes
                    while (cur != tail) { // set all afterward nodes value to 0, e.g. 1(cur)->9->9(tail)->7 + 4 -> 2->0->0->1
                        cur = cur->next;
                        cur->val = 0;
                    }
                }
                ListNode* node = new ListNode(val);
                tail->next = node;
                tail = node;
                if (tail->val < 9) cur = tail; // if the value is less than 9, it has the capacity to take an afterward carry
            }
            
            return head->val ? head : head->next; 
        }
    };
    

Log in to reply
 

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