# C++ solution: linear time and O(1) space except answer itself (32ms, non-recursive)

• Not sure if anyone got the same idea, but doesn't seem to appear in some top voted posts.

The "frontier" pointer stands for the nodes (possibly) impacted by carry and nearest to the list head. And "head" node is more like a helper node storing the carry propagated to the head.

``````    int count(ListNode* n) {
int ret =0 ;
while(n) ++ret, n = n->next;
return ret;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int c1 = count(l1), c2 = count(l2);
if(c1 > c2) swap(c1,c2), swap(l1,l2);
for(int i=0;i<c2-c1;++i, l2 = l2->next) {
n = n->next = new ListNode(l2->val);
if(n->val < 9) frontier = n;
}
for(;l1;l1 = l1->next, l2 = l2->next) {
n = n->next = new ListNode(l1->val + l2->val);
if(n->val < 9) frontier = n;
else if(n->val > 9) {
frontier->val +=1;
frontier = frontier->next;
while(frontier != n) {
frontier->val = 0;
frontier = frontier->next;
}
n->val -= 10;
}
}
ListNode* n2 = new ListNode(1);
n = n2;