Very clean O(n) C++ solution - no reversal


  • 0
    D

    The trivial way to do this is boil the problem into one where the least significant digits are at the heads of each list via reversal. Going one step further we could just put the values in two different vectors, and sum them (with or without reversing) easily since we have O(1) indexing.

    My solution deals with the lists exactly as they are. For now let's assume the lists are of equal length. The goal is to run from the end of the lists to the beginning. This tells me that we'll need a recursive call off the bat in our function, and some computation after the call. Assume we've recursed all the way to the end. We want to

    • Sum the values of these least significant digits + carry (carry init 0)
    • Push this value to our return linked list
    • Pass the carry value to the previous suspended stack frame, so it can use it in its addition

    Summing the values is trivial and pushing values to a linked list in O(1) time is trivial since keep adding on to our head and slowly inch away from the tail. So how do we ensure the previous stack frame can get access to the carry result of or addition? Note carry = (a->val + b->val + carry) % 10. Well we can either use a static variable (often messy), or a parameter passed by reference! Now when we assign the carry parameter a new value, we can ensure the previous stack frame can see it.

    Let's consider the case where the lists are not the same length.

    • 1 -> 2
    • 4 -> 5 -> 6

    Assuming we know the lengths of the list (easily computable) we know that since the second list is longer than the first by 1 node, we'll want to eventually be dealing with the first 1 node(s) of the longer list on their own and not be summing them with any values of the shorter list. This means we can recurse as we normally would, however just taking into account only one lists's values until the length of the remaining nodes are of the same length.

    It can be advantageous to know which list is the shorter one and which is the longer one. An easy way to do this without a bunch of if-elses riddled about the code duplicating each others work is to discover which one is longer (if lengths are not equal), and then call a helper function with the longer one as the first parameter.

    Full explanation: here

    // Source: https://leetcode.com/problems/add-two-numbers-ii/
    class Solution {
    public:
    
        int lengthOfList(ListNode *head) {
          int returnLength = 0;
    
          while (head) {
            returnLength++;
            head = head->next;
          }
    
          return returnLength;
        }
    
        ListNode* addTwoNumbersHelper(ListNode *a, ListNode *b, int aLen, int bLen, int& carry) {
          if (!a && !b) return NULL;
    
          if (aLen != bLen) {
            ListNode *next = addTwoNumbersHelper(a->next, b, aLen - 1, bLen, carry);
            ListNode *returnHead = new ListNode((a->val + carry) % 10);
            returnHead->next = next;
            carry = (a->val + carry) / 10;
            return returnHead;
          }
    
          ListNode *next = addTwoNumbersHelper(a->next, b->next, aLen - 1, bLen - 1, carry);
          ListNode *returnHead = new ListNode((a->val + b->val + carry) % 10);
          returnHead->next = next;
          carry = (a->val + b->val + carry) / 10;
          return returnHead;
        }
    
        ListNode* addTwoNumbers(ListNode *a, ListNode *b) {
          int aLen = lengthOfList(a), bLen = lengthOfList(b), carry = 0;
          ListNode *returnHead;
          if (aLen >= bLen) returnHead = addTwoNumbersHelper(a, b, aLen, bLen, carry);
          else returnHead = addTwoNumbersHelper(b, a, bLen, aLen, carry);
    
          if (carry) {
            ListNode *preHead = new ListNode(carry);
            preHead->next = returnHead;
            return preHead;
          }
    
          return returnHead;
        }
    };
    

Log in to reply
 

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