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

• ``````class Solution {
private:
int n = 0;
++n;
}
return n;
}
}
}
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
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);
l1 = l1->next;
--n1;
}
while (l1) {
int carry = l1->val + l2->val;
ListNode *p = new ListNode(carry % 10);
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;
}
}
};
``````

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
``````

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