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

• 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* 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;
}