C++ Solution without reverse. O(n) time and O(1) space. Beats 85%.


  • 0
    M

    My C++ Solution without reverse. O(n) time and O(1) extra space. Beats 85%.

    Q1. You may always reverse the linked-list, that is easy. But what about if you cannot reverse the linked-list l1 and l2. What about if you cannot reverse even the output linked-list?

    Q2. Many people uses vectors or stacks to avoid reversing the linked-list. That uses extra O(n) space and make Q1 trivial.

    Q3. What is the range of values when two digits between 0 and 9 add up?

    Observation: Two digits between 0-9 can add up to values between 0-18. The number carried to the higher digit can only be 0 or 1.

    • if sum > 9, then the higher digit always gets a carried 1 from current digit.
    • if sum < 9, then the higher digit never gets a carried 1.
    • if sum == 9, then it depends. If current digit gets a carried 1 itself, then it adds up to 10, current digit becomes 0 and 1 is carried to the higher digit. Otherwise, it remains 9 and no digit is carried further.

    Use this observation, one can use two pointers: One (h3) marks the lowest not-9 digit; another moves one digit at a time. The result is a linear time solution.

    Code:

    class Solution {
      public:
      ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        int len1=0, len2=0; // length of l1, l2
        
        ListNode *h1=l1; // runner for l1
        ListNode *h2=l2; // runner for l2
        
        // linear time, find length 
        while (h1!=NULL){
            h1 = h1->next;
            len1++;
        }
        while (h2!=NULL){
            h2 = h2->next;
            len2++;
        }
        
        // swap l1, l2 to make sure l1 is longer
        if (len1<len2){
            h1 = l2;
            h2 = l1;
        } else {
            h1 = l1;
            h2 = l2;
        }
            
        // build new linked list filled with sum
        ListNode* head = new ListNode(0);
        ListNode* h3 = head; // runner to marked the lowest not-9 digit
        ListNode* h4 = head; // another runner
        
        // run along l1 for extra digits 
        for (int i=0;i<abs(len1-len2);i++){
            ListNode* node = new ListNode(h1->val);
            h4->next = node;
            h4 = node;
            if (h1->val != 9){
                h3 = h4;
            }
            /* if h1->val == 9 then don't move h3.
            h3 marks the lowest not-9 digit */
            h1 = h1->next;
        }
        
        // run along l1, l2 simultaneously.
        while (h1 != NULL){
            int val = h1->val + h2->val;
            ListNode* node = new ListNode(val%10); // new is neccessary since a new linked list is built
            h4->next = node;
            h4 = node; 
            // if val > 9, change all previous 9 to 0 and add 1 to the val of h3.
            if (val > 9){
                h3->val++;
                while (h3->next != h4){
                    h3 = h3->next;
                    h3->val = 0;
                }
                h3 = h4;
            // if val < 9, move h3 to h4 without any mods of previous nodes 
            } else if (val < 9) {
                h3 = h4;
            }
            // if val == 9, don't move h3, just move h4.
            
            // move h1, h2
            h1 = h1->next;
            h2 = h2->next;
        }
        
        // if head get a carried 1, then return head, otherwise, return head->next.
        return (head->val > 0) ? head : head->next; 
    }
    };

Log in to reply
 

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